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):

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

print(" ".join(list(map(str,a))))
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
        print(" ".join(list(map(str,A))))

insertionSort(a,n)

Solution (Python):
length=int(input())
firstArray=input()
listForArray=list(map(int,firstArray.split()))
listForPrint=[firstArray]


def insertionSort(list,length):
    index=1
    while index<length:
        if listForArray[index]<=listForArray[index-1]:
            for index2 in range(0,index):
                if listForArray[index2-1]<=listForArray[index] and listForArray[index]<=listForArray[index2] or index2==0 and listForArray[index]<=listForArray[index2]:
                    newCommer=listForArray[index]
                    n=index
                    while n>index2:
                        listForArray[n]=listForArray[n-1]
                        n-=1
                    listForArray[index2]=newCommer
                    break   
        nowArray=str(listForArray[0])
        for index3 in range(1,length):
            nowArray+=" "+str(listForArray[index3])
        listForPrint.append(nowArray)
        index+=1    

insertionSort(listForArray,length)
for array in listForPrint:
    print(array)

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

for i in range(0, len(a)) :
    repl = i
    cur_num = a[i]
    
    
    for j in range(i, -1, -1) :
        if a[j] >= a[i] :
            repl = j
    
    
    for k in range(i, repl - 1, -1) :
        a[k] = a[k - 1]
    
    a[repl] = cur_num
    
    print(" ".join(map(str, a)))

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


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

insertionSort(cards, number)

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 -= 1
        A[j + 1] = v
        B = A.copy()
        for t in range(N):
            B[t] = str(B[t])
        print(" ".join(B))


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

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-=1
        a[j+1]=v
    print(*a)

Solution (Python):
def print_list(A):
    print(*A, sep=" ")

def insertion_sort(A, n):
    print_list(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_list(A)

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

insertion_sort(A, n)

Solution (Python):
def main():
    n = int(input())
    Mtx = list(map(int, input().split()))
    
    showMtx(Mtx)
    for i in range(1,n):
        for j in range(i,0,-1):
            if Mtx[j] < Mtx[j-1]:
                Mtx[j-1], Mtx[j] = Mtx[j], Mtx[j-1]
            
        showMtx(Mtx)
                

def showMtx(Mtx):    
    q = len(Mtx)
    for i in range(q):
        if i != q - 1:
            print(Mtx[i], sep=' ', end=' ')
        else:
            print(Mtx[i])



if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    Mtx = list(map(int, input().split()))
    
    showMtx(Mtx)
    for i in range(1,n):
        for j in range(i,0,-1):
            if Mtx[j] < Mtx[j-1]:
                Mtx[j-1], Mtx[j] = Mtx[j], Mtx[j-1]
            else:
                break
            
        showMtx(Mtx)
                

def showMtx(Mtx):    
    q = len(Mtx)
    for i in range(q):
        if i != q - 1:
            print(Mtx[i], sep=' ', end=' ')
        else:
            print(Mtx[i])



if __name__ == '__main__':
    main()

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

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

insertion_sort(nums, n)

Solution (Python):
import sys

n = input()
sort_list = list()

sort_list = map(int, raw_input().split())

for i in range(0,n):
    
    
    tmp = sort_list[i]
    j = i - 1
    while j >= 0 and sort_list[j] > tmp:
        sort_list[j+1] = sort_list[j]
        j = j - 1

    sort_list[j+1] = tmp


    for k in range(0,n):
        sys.stdout.write(str(sort_list[k]))
        if k is not n - 1:
            sys.stdout.write(" ")
        elif i is not n - 1:
            sys.stdout.write("\n")
            
print("")

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())
a = list(map(int, input().split()))

for i in range(n):
    for j in range(i):
        if a[j] > a[i]:
            a.insert(j, a[i])
            a.pop(i+1)
            break
    show(a)

Solution (Python):



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

n = int(input())
a = [int(i) for i in input().split()]
insertion_sort(a)
print(" ".join(map(str, a)))

Solution (Python):



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

n = int(input())
a = [int(i) for i in input().split()]
insertion_sort(a)
print(" ".join(map(str, a)))

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):
    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, = 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 insertion_sort(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
        print(' '.join([str(i) for i in a]))


n = int(input())
a = [int(i) for i in input().split()]
print(' '.join([str(i) for i in a]))

insertion_sort(a, n)

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):
def insertionSort(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 = list(map(int, input().split()))
insertionSort(A,N)

Solution (Python):
n = int(raw_input())
a = map(int, raw_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):
def insert_sort(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; print(*A)

N = int(input())
A = [int(n) for n in input().split()]; print(*A)
insert_sort(A, N)

Solution (Python):





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


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
        formatting(A)


N = int(input())
inputList = list(map(int, input().split()))

formatting(inputList)
insertionSort(inputList, N)

Solution (Python):
input()
myarr = list(map(int, input().split()))
for i in range(len(myarr)):
    for j in range(i, 0,-1):
        if myarr[j] < myarr[j-1]:
            t = myarr[j]
            myarr[j] = myarr[j-1]
            myarr[j-1] = t
        else:
            break
    print(" ".join(map(str, myarr)))

Solution (Python):

num = int(input())


array = list(map(int, input().split()))

def print_array():
    for i in range(num):
        if i != num-1:
            print(array[i], end=' ')
        else:
            print(array[i])



for i in range(num):
    insert = array[i]
    j = 0
    while array[j] < insert:
        j+=1
    for k in range(i, j, -1):
        array[k] = array[k - 1]
    array[j] = insert
    print_array()

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Solution (Python):
def insertion_sort(A, N):
    yield 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
        yield A

N = int(input())
A = list(map(int, input().split()))
for li in insertion_sort(A, N):
    print(*li)

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


for i in range(N):
    if N == 1:
        print(A[0])
        break
    j = i

    while j > 0 and A[j] < A[j-1]:
        if A[j] > A[j-1]:

            break
        k = A[j]
        l = A[j-1]
        A[j-1] = k
        A[j] = l
        j -= 1

    S = str(A[0])
    for k in range(1,N-1):
        S += " " + str(A[k])

    S = S + " "+str(A[N-1])
    print(S)

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

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())
A=[int(i) for i in input().split()]
S=""
for i in range(N-1):
    S=S+str(A[i])+" "
S=S+str(A[N-1])
print(S)
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
    S=""
    for i in range(N-1):
        S=S+str(A[i])+" "
    S=S+str(A[N-1])
    print(S)

Solution (Python):
def insertionSort(a, n):
    trace(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
        trace(a, n)


def trace(a, n):
    output = ''
    for i in a:
        if i == a[n-1]:
            output += str(i)
        else:
            output += str(i) + ' '
    print(output)

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

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

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

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

def insertionSort(A, N):
    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 -= 1
        A[j+1] = v
        print(*A)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    _ = input()
    array = [int(x) for x in input().split()]
    print(" ".join(map(str, array)))

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


main()

Solution (Python):
N = int(input())
A = list(map(int, input().split(" ")))
for k in range(len(A)-1):
    print(A[k], end= " ")
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 k in range(len(A)-1):
        print(A[k], end= " ")
    print(A[-1])

Solution (Python):
def showList(A, N):
    for i in range(N-1):
        print(A[i],end=' ')
    print(A[N-1])

def insertionSort(A, N):
    showList(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
        showList(A,N)


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

A = insertionSort(A, N)

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 -= 1
    A[j + 1] = v
    print(*A)

Solution (Python):
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
        show(A)
        
     
def show(nums):
    for i in range(len(nums)):
        if i != len(nums) - 1:
            print(nums[i],end=' ')
        else:
            print(nums[i])
A = []
N = int(input())
A = list(map(int,input().split()))

show(A)
insertionSort(A,N)

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

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

def insertion(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
        trace(a)
    


trace(a)
insertion(a)

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
    ans = ' '.join(map(str,a))
    print(ans)

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 out(data) -> str:
    print(' '.join(map(str, data)))


N = int(input())
data = [int(i) for i in input().split()]
out(data)
for i in range(1, N):
    tmp = data[i]
    j = i - 1
    while j >= 0 and data[j] > tmp:
        data[j + 1] = data[j]
        j -= 1
    data[j + 1] = tmp
    out(data)

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

def insertion_sort(A, N):
    for i in range(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

        string = list(map(str, A))
        print(' '.join(string))

insertion_sort(A, N)

Solution (Python):
from sys import stdin
 
n = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().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
    else:
        A[j+1] = v
        print(*A)

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):
    j = i
    while a[j - 1] > a[j] and j > 0:
        a[j], a[j - 1] = a[j - 1], a[j]
        j -= 1
    print(" ".join([str(i) for i in a]))

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())
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 v < a[j]:
        a[j+1] = a[j]
        j -= 1

    a[j+1] = v

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

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

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

data = input().split()

array = []

for i in data:
  array.append(int(i))

for i in range(1, n):
  print(*array)

  key = array[i]

  j = i - 1

  while j >= 0 and array[j] > key:
    array[j+1] = array[j]
    j -= 1

  array[j+1] = key 

print(*array)

Solution (Python):

def trace(A, N):
    for i in range(int(N)-1):
        print(A[i], end=' ')
    print(A[int(N)-1])

def insertionSort(A, N):
    for i in range(1, int(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
        trace(A, N)

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

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 -= 1
    A[j+1] = v
    print(*A)

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

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

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

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

for i in range(num):
	v = A[i]
	j = i -1

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

	
	list2 = [str(k) for k in A]
	print(" ".join(list2))

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

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

        outputNum(A)

def outputNum(A):
    tmp = map(str,A)
    text = " ".join(tmp)
    print(text)

outputNum(A)
insertionSort(A,N)

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(map(str,l)))
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
        print(" ".join(map(str,a)))
insertionSort(l,n)

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(' '.join(list(map(str,a))))

Solution (Python):
def main():
    N = int(input())
    L = list(map(int, input().split()))

    for i in range(1, N):
        print(*L)
        tmp = L[i]
        j = i
        while j > 0 and L[j-1] > tmp:
            L[j] = L[j-1]
            j -= 1
        L[j] = tmp

    print(*L)


if __name__ == '__main__':
    main()

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

def sort(N,A):
    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
        pr(A)

def pr(list):
    n = len(list)
    for i in range(n):
        if i < n-1:
            print(list[i],end=" ")
        else:
            print(list[i],end="\n")

sort(N,A)

Solution (Python):

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

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):


def printline(data):
    l=""
    for i,s in enumerate(data):
        l = l + str(s)
        if i+1 != len(data):
            l = l+" "
    print(l)


length = int(input())
data = list(map(int,input().split()))
printline(data)
for i in range(1,len(data)):
    tmp = data[i]
    i2 = i - 1
    while i2 >=0 and data[i2] > tmp:
        data[i2+1] = data[i2]
        i2 -= 1

    data[i2+1] = tmp
    printline(data)

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

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

Solution (Python):
def insertion_sort(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
        
        print(*A)

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

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())
a = list(map(int,input().split()))

for i in range(1,n):
	print(*a)
	j = i -1
	v = a[i]
	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(0,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, sep=" ")

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

Solution (Python):
def insertionSort(A,N):
    for i in range(0,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, sep=" ")

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

Solution (Python):
def insertion_sort(A):
    n = len(A)
    print(*A)
    for i in range(1, n):
        item = A[i]
        cur_idx = i - 1
        while cur_idx >= 0 and A[cur_idx] > item:
            A[cur_idx], A[cur_idx + 1] = A[cur_idx + 1], A[cur_idx]
            cur_idx -= 1
        print(*A)


if __name__ == "__main__":
    N = int(input())
    A = [int(elem) for elem in input().split()]
    insertion_sort(A)

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

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

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

Solution (Python):
def main():
    number = int(raw_input())
    list = map(int, raw_input().split())
    sort(number, list)

def sort(number, list):
    output(list)
    for i in range(1, number):
        key = list[i]
        j = i - 1
        while j >= 0 and list[j] > key:
            list[j+1] = list[j]
            j -= 1
        list[j+1] = key
        output(list)

def output(list):
    print(" ".join(map(str, list)))

main()

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

for i in range(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(map(str, a)))

Solution (Python):
N = input();
A = map(int,raw_input().split(" "))
for i in range(1,len(A)):
	key = A[i]
	j = i - 1;
	for k in range(0,len(A)):
		if A[N-1] == A[k]:
			print A[k]
		else:
			print A[k],
	while j >=0 and A[j] > key:
		A[j+1] = A[j]
		j -= 1
	A[j+1] = key
for j in range(0,len(A)):
		if A[N-1] == A[j] :
			print A[j]
		else:
			print A[j],

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

Solution (Python):
n = raw_input()

A = map(int, raw_input().split())

for i, key in enumerate(A):

    j = i - 1

    while(j >= 0 and A[j] > key):
        A[j+1] = A[j]
        j -= 1

    A[j+1] = key

    for x in A:
        print x,
    print

Solution (Python):
import sys

N = int(raw_input())
A = map(int, raw_input().split())
a_str = map(str, A)
print(" ".join(a_str))
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
	a_str = map(str, A)
	print(" ".join(a_str))

Solution (Python):
n = input()
A = list(map(int, 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=input()
num_list=[int(x) for x in raw_input().split(" ")]

for idx in range(1, len(num_list)):
    print " ".join([str(x) for x in num_list])
    key=num_list[idx]
    jdx = idx - 1
    
    while jdx >= 0 and num_list[jdx] > key:
        num_list[jdx+1] = num_list[jdx]
        jdx -= 1
    num_list[jdx+1] = key
print " ".join([str(x) for x in num_list])

Solution (Python):
N = int(raw_input())
A = map(int,raw_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):
def insertion_sort(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 = j-1
        A[j+1] = v

        print(*A)

if __name__ == '__main__':
    N = int(input())
    A = [int(_) for _ in input().split()]

    print(*A)

    insertion_sort(A, N)