Problem:
Insertion Sort Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode: for i = 1 to A.length-1
    key = A[i]
    /* insert A[i] into the sorted sequence A[0,...,j-1] */
    j = i - 1
    while j >= 0 and A[j] > key
        A[j+1] = A[j]
        j--
    A[j+1] = key Note that, indices for array elements are based on 0-origin. To illustrate the algorithms, your program should trace intermediate result for each step. Input The first line of the input includes an integer N, the number of elements in the sequence. In the second line, N elements of the sequence are given separated by a single space. Output The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space. Constraints 1 ≤ N ≤ 100 Sample Input 1 6
5 2 4 6 1 3 Sample Output 1 5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6 Sample Input 2 3
1 2 3 Sample Output 2 1 2 3
1 2 3
1 2 3 Hint Template in C

Solution (Python):
def insertionSort(At, Nt):
	for i in range(Nt):
		v = At[i]
		j = i - 1
		while j >= 0 and At[j] > v:
			A[j + 1] = A[j]
			j = j - 1
		A[j + 1] = v
		print(" ".join(map(str,At)))
	return At

if __name__ == '__main__':
	N = int(input())
	A = list(map(int, input().split()))
	A = insertionSort(A, N)

Solution (Python):
n = int(input())
sortlist = list(map(int,input().split()))

print(' '.join(map(str, sortlist)))
for i in range(1,n):
    temp = sortlist[i]
    if temp < sortlist[i-1]:
        j = i
        while True:
            sortlist[j] = sortlist[j-1]
            j -= 1
            if j ==0 or temp >= sortlist[j-1]:
                break
        sortlist[j] = temp
        print(' '.join(map(str, sortlist)))
    else:
        print(' '.join(map(str, sortlist)))

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
print(*A)
for i in range(1, len(A)):
    key = A[i]
    j = i-1
    while j>=0 and A[j]>key:
        A[j+1]=A[j]
        j -= 1
    A[j+1]=key
    print(*A)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
for i in range(0, n-1):
    print(a[i], end=" ")
print(a[n-1])
for i in range(1, n):
    v = a[i]
    j = i-1
    while j>=0 and a[j]>v:
        a[j+1] = a[j]
        j-=1
    a[j+1] = v
    for i in range(0, n-1):
        print(a[i], end=" ")
    print(a[n-1])

Solution (Python):
def nsertionSort(A, N): 
    print(" ".join(map(str,A)))
    for i in range(1,N,1):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j-=1
            A[j+1] = v
        print(" ".join(map(str,A)))

if __name__ == "__main__":
    N = int(input())
    A = list(map(int,input().split()))
    nsertionSort(A,N)

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

def printlist(l):
    print(' '.join(map(str, l)))

def insertion_sort(a, n):
    for i in range(1, n):
        printlist(a)
        v = a[i]
        j = i-1
        while j >= 0 and a[j] > v:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v

insertion_sort(a,n)
printlist(a)

Solution (Python):
n = int(input().strip())
a = [int(s) for s in input().strip().split(' ')]
for i in range(1, n):
    print(' '.join((str(i) for i in a)))
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = v

print(' '.join((str(i) for i in a)))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

def insertion_sort(A, N):
    for i in range(N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j]>v:
            A[j+1]=A[j]
            j -= 1
        A[j+1] = v
        print(' '.join(map(str, A)))

insertion_sort(A, N)

Solution (Python):
cnt=int(input())
*card,=map(int,input().split())
for i in range(cnt):
	v=card[i]
	j=i-1
	while j>=0 and card[j]>v:
		card[j+1]=card[j]
		j-=1
	card[j+1]=v
	print(*card)

Solution (Python):
def main():
	n = int(input())
	a = list(map(int, input().split()))
	printlist(a)
	insertionSort(a, n)

def insertionSort(a, n):
	for i in range(1,n):
		v = a[i]
		j = i - 1
		while j >= 0 and a[j] > v:
			a[j + 1] = a[j]
			j -= 1
		a[j+1] = v
		printlist(a)

def printlist(a):
	values = map(str, a)
	print(' '.join(values))

main()

Solution (Python):
def insertsort(array):
    for i in range(1,len(array)):
        print(" ".join(list(map(str,array))))
        temp = array[i]
        j = i-1
        while j >= 0 and temp < array[j]:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = temp
    return array

input()
a = insertsort(list(map(int,input().split())))
print(" ".join(list(map(str,a))))

Solution (Python):
import copy
n = int(input())
l = list(map(int, input().split()))
s = copy.deepcopy(l)
m = 1
print(*s)
for i in range(1,n):
    count = 0
    for j in range(0,m):
        if s[i] < l[j]:
            l.insert(j, l[i])
            l.pop(i+1)
            m+=1
            count += 1
            break
    if count == 0:
        l.insert(m, l[i])
        l.pop(i+1)
        m+=1

    print(*l)

Solution (Python):
N = int(input())
a = list(map(int,input().split()))
x = ' '.join(map(str, a))
print(x)

for i in range(1,N):
	v = a[i]
	j = i - 1
	while j >= 0 and a[j] > v:
		a[j+1] = a[j]
		j = j - 1
	a[j+1] = v
	x = ' '.join(map(str, a))
	print(x)

Solution (Python):
n = int(input())

a = input().split()

a = [int(x) for x in a]


for i,x in enumerate(a):
    if i != len(a)-1:
        print(x, end=" ")
    else:
        print(x, end="")
print()

for i in range(1, len(a)):
    v = a[i]
    j = i-1

    while j>= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1

    a[j+1] = v

    for i,x in enumerate(a):
        if i != len(a)-1:
            print(x, end=" ")
        else:
            print(x, end="")
    print()

Solution (Python):
n=int(input())
lst=list(map(int,input().split()))
for i in range(n):
    x=lst[i]
    for j in range(i)[::-1]:
        if lst[j]<x:break
        lst[j+1]=lst[j]
        lst[j]=x
    print(*lst)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
for i in range(1, N + 1):
    A[:i] = sorted(A[:i])
    print(*A)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))

def hyouji(A):
    for z in range(len(A)):
        if z==0:
            print(A[z],end="")
        else:
            print(" "+str(A[z]),end="")
    print()

hyouji(A)
for i in range(1,N):
    v=A[i]
    j=i-1

    while j>=0 and A[j]>v:
        A[j+1]=A[j]
        j=j-1
    A[j+1]=v

    hyouji(A)

Solution (Python):


N = int(input())
aN = list(map(str, input().split()))

for i in range(N):
    tmp = aN[i]
    j = i - 1
    while j >= 0 and int(aN[j]) > int(tmp):
        aN[j+1] = aN[j]
        j -= 1
    aN[j+1] = tmp

    print(' '.join(aN))

Solution (Python):
N = int(input())
*A, = list(map(int, input().split()))
for i in range(N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    print(*A)

Solution (Python):
def insertionSort(a, n):
    for i in range(n):
        if i != n-1:
            print(a[i], end=" ")
        else:
            print(a[i], end="")
    print("")
    for i in range(1, n):
        v = a[i]
        j = i - 1
        while j >= 0 and a[j] > v:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        for i in range(n):
            if i != n-1:
                print(a[i], end=" ")
            else:
                print(a[i], end="")
        print("")

if __name__ == '__main__':
    n = int(input())
    a = []
    a = list(map(int, input().split()))
    insertionSort(a, n)

Solution (Python):



n = int(input())
l = list(map(int,input().split()))
print (' '.join(map(str,l)))
for i in range(1,n):
    v = l[i]
    j = i -1
    while (j>=0 and l[j]>v ):
        l[j+1] = l[j]
        j -= 1
        l[j+1] = v
    print (' '.join(map(str,l)))

Solution (Python):
def insertion_sort(n, nums):
    print(' '.join(map(str,nums)))
    for i in range(1, n):
        v = nums[i]
        j = i -1
        while j>=0 and v < nums[j]:
            nums[j+1] = nums[j]
            j-=1
        nums[j+1] = v
        print(' '.join(map(str,nums)))


def main():
    n = int(input())
    line = input()
    nums = list(map(int, line.split()))

    insertion_sort(n, nums)

if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]

def show():
    maplist=map(str, A)
    maplist=' '.join(maplist)
    print(maplist)
show()
for i in range(1,n):
    key=A[i]
    j=i-1
    while j>=0 and A[j]>key:
        A[j+1]=A[j]
        j-=1
    A[j+1]=key
    show()

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
print(" ".join(map(str,l)))
for i in  range(1,n):
    v = l[i]
    j = i - 1
    while j >= 0 and l[j] > v:
        l[j+1] = l[j]
        j-=1
    l[j+1] = v
    print(" ".join(map(str,l)))

Solution (Python):
def insertion_sort(num_list):
    print(' '.join(num_list))

    for i in range(1,len(num_list)):
        popped_num = num_list[i]
        j = i-1
        while j >= 0 and int(num_list[j]) > int(popped_num):
            num_list[j+1] = num_list[j]
            j -=1
        num_list[j+1] = popped_num
        print(' '.join(num_list))


n = input()
num_list = list(input().split())
insertion_sort(num_list)

Solution (Python):
n = int(input())
array = list(map(int,input().split(" ")))
for i in range(0, n):
    v = array[i]
    j = i - 1
    while j >= 0 and array[j] > v:
        array[j+1] = array[j]
        j -= 1
    array[j+1] = v
    print(" ".join(list(map(str, array))))

Solution (Python):
n = int(input())
nlist = list(map(int, input().split()))

ans = nlist.copy

for i in range(n):
    v = nlist[i]
    j = i - 1
    while j >= 0 and nlist[j] > v:
        nlist[j+1] = nlist[j]
        j -= 1
    nlist[j+1] = v

    for j in range(n):
        if j == n-1:
            print(nlist[j])
        else:
            print(str(nlist[j]) + " ", end="")

Solution (Python):
import sys

def main():
    inputslen = int(sys.stdin.readline().rstrip())
    inputs= sys.stdin.readline()

    sortvalue = [int(i) for i in inputs.split()]
    for i in range(1, inputslen):
        printvalue = map(str, sortvalue)
        print(' '.join(printvalue))

        compvalue = sortvalue[i]
        j = i - 1
        while j >= 0 and sortvalue[j] > compvalue:
            sortvalue[j+1] = sortvalue[j]
            j -= 1
        sortvalue[j+1] = compvalue

    printvalue = map(str, sortvalue)
    print(' '.join(printvalue))

if __name__ == '__main__':
    main()

Solution (Python):
def show(nums):
    for i in range(len(nums)):
        if i!=len(nums)-1:
            print(nums[i],end=' ')
        else:
            print(nums[i])


n=int(input())
nums=list(map(int,input().split()))
show(nums)
for i in range(1,n):
    v=nums[i]
    j=i-1
    while(j>=0 and nums[j]>v):
        nums[j+1]=nums[j]
        j-=1
    nums[j+1]=v
    show(nums)

Solution (Python):
N= int(input())
nums= list(map(int,input().split(" ")))
for x in range(N):
        if(x!=N-1):
            print(nums[x],end=" ")
        else:
            print(nums[x])
for i in range(1,N):
    a= nums[i]
    j=i-1
    while nums[j]>a and j>=0:
        nums[j+1]=nums[j]
        j-=1
    nums[j+1]=a
    for x in range(N):
        if(x!=N-1):
            print(nums[x],end=" ")
        else:
            print(nums[x])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
print(" ".join(list(map(str, A))))
for i in range(1, N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    print(" ".join(list(map(str, A))))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
print(' '.join(list(map(str,a))))
for i in range(1,n):
	v=a[i]
	j=i-1
	while j>=0 and a[j]>v:
		a[j+1]=a[j]
		a[j]=v
		j-=1
	print(' '.join(list(map(str,a))))

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
for i in range(1, n):
    print(' '.join(map(str, A)))
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key
print(' '.join(map(str, A)))

Solution (Python):
N = int(input())
lst = list(map(int, input().split()))
def printInt(L):
    print(" ".join(map(str, L)))
for i in range(N):
    j = 0
    while j < i:
        if lst[j] > lst[i]:
            break
        j += 1
    tmp = lst[i]
    for x in range(i, j, -1):
        lst[x] = lst[x - 1]
    lst[j] = tmp
    printInt(lst)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
print(" ".join(map(str,a)))
for i in range(1,n):
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = v
    print(" ".join(map(str,a)))

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
print(" ".join(list(map(str,l))))
for i in range(1,n):
    x=l[i]
    for j in range(0,i)[::-1]:
        if(l[j] <= x):
            j+=1
            break
    del l[i]
    l.insert(j,x)
    print(" ".join(list(map(str,l))))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

for k in range(N):
        print(A[k], end='')
        if k < N-1:
            print(' ', end='')
print('')

for i in range(1, N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    for k in range(N):
        print(A[k], end='')
        if k < N-1:
            print(' ', end='')
    print('')

Solution (Python):
def print_list(r):
    for i in range(len(r)):
        if i != len(r)-1:
            print (r[i], end=' ')
        else:
            print(r[i])


n=int(input())
r=list(map(int,input().split()))
for i in range(0, len(r)):
        v = r[i]
        j = i-1
        while (j >= 0) & (r[j] > v):
            r[j+1] = r[j]
            j -= 1
        r[j+1] = v
        print_list(r)

Solution (Python):
N = input()
A = map(int,raw_input().split())
 
for i in range(N-1):
    print A[i],
print A[-1]
 
for i in range(1,N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    for i in range(N-1):
        print A[i],
    print A[-1]

Solution (Python):
def insertionSort(a: list, n: int):
    for i in range(1, n):
        v = a[i]
        j = i - 1
        while j >= 0 and a[j] > v:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        a_str = map(str, a)
        print(" ".join(a_str))

n = int(input())
a = list(map(int, input().split()))
a_str = map(str, a)
print(" ".join(a_str))
insertionSort(a, n)

Solution (Python):
n = int(input())
list_n = list((map(int, input().split())))
def insertionSort(list_a, n):
    for i in range(1,n):
        v = list_a[i]
        j = i - 1
        while j >= 0 and list_a[j] > v:
            list_a[j+1] = list_a[j]
            j -= 1
        list_a[j+1] = v
        print(" ".join([str(number) for number in list_a]))
print(" ".join([str(number) for number in list_n]))
insertionSort(list_n, n)

Solution (Python):
def InsertionSort(A):
    print(' '.join(map(str, A)))
    for i in range(1,len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j-=1
            A[j+1] = key
        print(' '.join(map(str, A)))

    return A

input()
a=[i for i in map(int, input().split())]
InsertionSort(a)

Solution (Python):
def insertionSort(a,n):
	for i in range(n):
		v=a[i]
		j=i - 1
		while j>=0 and a[j]>v:
			a[j+1]=a[j]
			j=j-1
		a[j+1]=v
		print(' '.join(map(str,a)))

n = int(input())
a = list(map(int,input().split()))
insertionSort(a,n)

Solution (Python):
def insertion(A,N):
    for i in range(1,N):
        print(" ".join([str(k) for k in A]))
        v=A[i]
        j=i-1
        while j>=0 and A[j]>v:
            A[j+1]=A[j]
            j-=1
        A[j+1]=v

n=int(input())
A=list(map(int,input().split()))
insertion(A,n)
print(" ".join([str(k) for k in A]))

Solution (Python):

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

for i in range(1, n):
    print(" ".join(map(str, nums)))
    v = nums[i]
    j = i - 1
    while j >= 0 and nums[j] > v:
        nums[j + 1] = nums[j]
        j -= 1
    nums[j + 1] = v

print(" ".join(map(str, nums)))

Solution (Python):
def print_list(A):
    print(" ".join(list(map(str, A))))

def main():
    N = int(input())
    A = list(map(int, input().split()))

    print_list(A)

    for i in range(1, N):
        store_v = A[i]
        
        j = i - 1
        while j >= 0 and A[j] > store_v:
            A[j + 1] = A[j]
            j -= 1

        A[j+1] = store_v

        print_list(A)

main()

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
 
def insertionSort(arr):
    arr_len = len(arr)
    for i in range(arr_len):
        v = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > v :
            A[j +1] =A[j]
            j = j -1
        arr[j+1] = v
        print(' '.join([str(x) for x in arr]))
 
insertionSort(A)

Solution (Python):
def Output(A):
    print(' '.join(list(map(str, A))))

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(1, N):
        Output(A)
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = v
    Output(A)

if __name__ == '__main__':
    main()

Solution (Python):

n=int(input())
*l,=list(map(int,input().split()))

for i in range(n):
    temp=l[i]
    j=i-1
    while j>=0 and l[j]>temp:
        l[j+1] = l[j]
        j-=1
    l[j+1] = temp
    print(*l)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
print(*a)
for i in range(1, n):
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j + 1] = a[j]
        j = j - 1
    a[j + 1] = v
    print(*a)

Solution (Python):
n = int(input())
a = [int(_) for _ in input().split()]
for i in range(n-1):
    print(a[i], end=" ")
print(a[n-1])
for i in range(1, n):
    insert = a[i]
    

    for j in range(i-1, -1, -1):
        
        if a[j] > insert:
            a[j+1] = a[j]
            a[j] = insert
        else:
            break
    for i in range(n-1):
        print(a[i], end=" ")
    print(a[n-1])

Solution (Python):



N = int(input())
l = input().split(' ')
A = [int(i) for i in l]


def insertion(A, N): 
    for i in range(N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = v
        map_list = map(str, A)
        a = ' '.join(map_list)
        print(a)

insertion(A, N)

Solution (Python):
N = int(input())
A = list(map(int, input().split() ) )

print( ' '.join(map(str, A)) )

for i in range(1, N):
    val = A[i]
    j = i - 1
    while j >= 0 and A[j] > val :
        A[j+1] = A[j]
        j -= 1
    A[j+1] = val
    print( ' '.join(map(str, A)) )

Solution (Python):
n = int(input())
a = list(map(int,input().split()))

for i in range(n):
    v = a[i]
    j = i-1
    while j>=0 and a[j]>v:
        a[j+1] = a[j]
        j -= 1
        a[j+1] = v
    print(*a)

Solution (Python):






cnt = int(input())
numbers = list(map(int, input().split(' ')))


def insertionsort(A, N):
    '''
    :param A: N個の要素を含む０オリジンの配列
    :param N: Aの要素数
    :return:
    '''
    print(' '.join(map(str, A)))

    for i in range(1, N):
        
        v = A[i]
        
        j = i - 1
        
        while j >= 0 and A[j] > v:
            
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v

        print(' '.join(map(str, A)))

insertionsort(numbers, cnt)

Solution (Python):
def main():
    input()
    sequence = list(map(int, input().split()))
    inserted = False
    for i in range(len(sequence)):
        n = sequence.pop(i)
        for j in sequence[:i]:
            if n <= j:
                sequence.insert(sequence.index(j), n)
                inserted = True
                break
        if inserted is False:
            sequence.insert(i, n)
        else:
            inserted = False
        print(' '.join(map(str,sequence)))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
cards = list(map(int, input().split()))

for i in range(n):
    v = cards[i]
    j = i-1
    while j >= 0 and cards[j] > v:
        cards[j+1] = cards[j]
        j -= 1
    cards[j+1] = v
    print(' '.join(map(str, cards)))

Solution (Python):
n = int(input())
A = [int(i) for i in input().split()]
print(' '.join([str(i) for i in A]))
for i in range(1, n):
    key = A[i]
    j = i - 1
    while j>=0 and A[j] > key:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = key
    print(' '.join([str(i) for i in A]))

Solution (Python):
N=int(input())
S=list(map(str,input().split()))

print(" ".join(S).rstrip())

for i in range(1,len(S)):
    
    for j in range(i):
        if int(S[j])>=int(S[i]):
            S.insert(j,S[i])
            del S[i+1]
    
        else:
            
            pass
    print(" ".join(S).rstrip())

Solution (Python):
def pr(A):
    N = len(A);
    for i in range(N):
        if i :
            print (" ", end = "");
        print (A[i], end = "")
    print ("")

def insertionSort(A):
    pr(A)
    N = len(A)
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = v
        pr(A)

N = int(input())
A = [int(i) for i in input().split()]

insertionSort(A)

Solution (Python):
N = int(input())
A =  list(map(int, input().split())) 

def output_ary():

    s = ''

    for x in A:

        s = s + str(x) + ' '
    
    print(s.rstrip())

output_ary()

i = 1

while i < N:

    V = A[i]

    j = i - 1

    while j >= 0 and A[j] > V:

        A[j + 1] = A[j]
        
        j -= 1
    
    A[j + 1] = V

    i += 1

    output_ary()

Solution (Python):

def insert_sort(A):
    array = A[:]
    for i in range(1, len(array)):
        print(' '.join(array))
        v = array[i]
        j = i - 1

        while j >= 0 and int(array[j]) > int(v):
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = v
    return array

_, A = input(), input().split()
print(' '.join(insert_sort(A)))

Solution (Python):
N = int(input())
S = list(map(int, input().split()))

j = 0
for i in range(N):
    key = S[i]
    j = i - 1
    while j>=0 and S[j] > key:
        S[j+1] = S[j]
        j-=1
    S[j+1] = key
    
    res = ""
    for i in range(N):
        res += str(S[i])
        if i < N-1:
            res += " "
    
    print(res)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
str_A = [str(a) for a in A]
result = ' '.join(str_A)
print(result)
for i in range(1, N, 1):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j + 1] = A[j]
        j -= 1
    A[j+1] = v
    str_A = [str(a) for a in A]
    result = ' '.join(str_A)
    print(result)

Solution (Python):
def insertionSort(N):
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and v < A[j]:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = v
        print(*A)

N = int(input())
A = list(map(int, input().split()))
print(*A)
insertionSort(N)

Solution (Python):
input()
x = list(map(int, input().split()))

def insertion_sort(a):
    print(*a)
    for i in range(1, len(a)):
        v = a[i]
        j = i - 1
        while j >= 0 and a[j] > v:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        print(*a)

insertion_sort(x)

Solution (Python):
def I_S(a,n):
	print(' '.join(map(str,a)))
	for i in range(1,n):
		v=a[i]
		j=i-1
		while j>=0 and a[j]>v:
			a[j+1]=a[j]
			j-=1
		a[j+1]=v
		print(' '.join(map(str,a)))
		
n=int(input())
a=[int(x) for x in input().split()]

I_S(a,n)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    v = A[i]
    j = i - 1
    print(' '.join(map(str, A)))
    while j >= 0 and A[j] > v:
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = v
print(' '.join(map(str, A)))

Solution (Python):
def inserts(N):
    k = 1
    for n in N:
        print(n, end='')
        if k < len(N):
            print(' ', end='')
        k += 1
 
    print('')
    for i in range(1,len(N)):
        v = N[i]
        j = i - 1
        while j >= 0 and N[j] > v:
            N[j + 1] = N[j]
            j -= 1
        N[j + 1] = v
        k = 1
        for n in N:
            print(n, end='')
            if k < len(N):
                print(' ', end='')
            k += 1
        print('')
 
 
n = int(input())
numbers = list(map(int, input().split()))
 
inserts(numbers)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

def insertionSort():
  for i in range(1, n):
    v = a[i]
    j = i-1
    while j>=0 and a[j]>v:
      a[j+1] = a[j]
      j -= 1
    a[j+1] = v
    print(" ".join(map(str, a)))

print(" ".join(map(str, a)))
insertionSort()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
  p = i - 1
  while p >= 0 and A[p] > A[p + 1]:
    A[p], A[p + 1] = A[p + 1], A[p]
    p -= 1
  for j in range(N):
    print(A[j], end = " \n"[j + 1 == N])

Solution (Python):
n = int(input())
s = input()
print(s)
s = s.split(" ")
for i in range(n):
    s[i] = int(s[i])
for i in range(1,n):
    v = s[i]
    j = i-1
    while j >= 0 and s[j] > v:
        s[j+1] = s[j]
        j -= 1
    s[j+1] = v
    for k in range(n-1):
        print(s[k],end = " ")
    print(s[n-1])

Solution (Python):
def insertion_sort(A,N):
	prin(A)
	for i in range(1,N):
		v = A[i]
		j = i-1
		while j >= 0 and A[j] > v:
			A[j+1] = A[j]
			j -= 1
		A[j+1] = v
		prin(A)
def prin(A):
	print(' '.join(list(map(str, A))))
N = int(input())
A = [int(i) for i in input().split(' ')]
insertion_sort(A,N)

Solution (Python):
def insertion_sort(A):
    print " ".join(map(str, A))
    for i in range(1, len(A)):
        key = A[i]
        
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = key
        print " ".join(map(str, A))

N = int(raw_input())
A = map(int, raw_input().split(" "))
insertion_sort(A)