🔥

문제

솔이는 삽입 정렬을 배웠지만 아직 삽입 정렬이 어떻게 수행되는지 이해가 가지 않는다고 한다.


그런 솔이를 위해 삽입 정렬이 진행되는 과정을 출력해주는 프로그램을 만들어주자.


수 이동은 최소로 하며, 이동이 일어날 때에만 그 결과를 출력해주면 된다.


여기서 수 이동이란, i번째 수가 삽입이 이루어질 때, 그 수가 이동한 것을 의미한다.
예를 들어, 1 3 4 5 2 6 8 7 에서 5번째에 있는 2가 삽입이 이루어진다고 하면 5, 4, 3 앞으로 이동하기 때문에 총 3번의 이동이 일어났다고 할 수 있다.

입력

첫째 줄에 데이터의 개수 n이 주어진다. (1≤n≤100)


둘째 줄에 정렬하고자 하는 데이터 n개가 공백을 사이에 두고 주어진다.

출력

처음 입력으로 주어진 상태부터 시작하여 교환이 일어나는 과정을 모두 출력하여라.

예제 1 입력

5
1 19 14 19 2

예제 1 출력

1 19 14 19 2
1 14 19 19 2
1 14 19 2 19
1 14 2 19 19
1 2 14 19 19

예제 2 입력

9
8 10 15 20 2 17 18 3 11

예제 2 출력

8 10 15 20 2 17 18 3 11
8 10 15 2 20 17 18 3 11
8 10 15 2 17 20 18 3 11
8 10 15 2 17 18 20 3 11
8 10 15 2 17 18 3 20 11
8 10 15 2 17 18 3 11 20
8 10 2 15 17 18 3 11 20
8 10 2 15 17 3 18 11 20
8 10 2 15 17 3 11 18 20
8 2 10 15 17 3 11 18 20
8 2 10 15 3 17 11 18 20
8 2 10 15 3 11 17 18 20
2 8 10 15 3 11 17 18 20
2 8 10 3 15 11 17 18 20
2 8 10 3 11 15 17 18 20
2 8 3 10 11 15 17 18 20
2 3 8 10 11 15 17 18 20

Source

n = int(input())
arr = list(map(int, input().split()))

print(*arr)

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if(arr[i - 1] > arr[i]):
                tmp = arr[i - 1]
                arr[i - 1] = arr[i]
                arr[i] = tmp
                print(*arr)

insertion_sort(arr)

참고