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):
num = int(input())
arr = list(map(int,input().split()))
print(" ".join(list(map(str,arr))))
def isn(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,arr))))

isn(arr,num)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
print(*a)
for i in range(len(a)-1):
    

    l = i
    j = l + 1


    while l >= 0:
        
        
        
        

        
        if a[j] < a[l]:
            
            temp = a[l]
            a[l] = a[j]
            a[j] = temp
            l -= 1
            j -= 1
            
        else:
            break
    print(*a)

Solution (Python):
import sys
input = sys.stdin.readline

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

def insertionSort(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)
print(*A)
insertionSort(N)

Solution (Python):


n=int(input())

l=[int(x) for x in input().split()]

for i in range(n):
    j=i
    while j>0 :
        if l[j-1]>l[j]:
            a=l[j]
            l[j]=l[j-1]
            l[j-1]=a
            j-=1
        else :
            break

    print(*l)

Solution (Python):
def func(n, A):
    for i in range(1, n):
        print (" ".join(map(str, 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(map(str, A)))

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

Solution (Python):
N=int(input())
A=[]
A=input().split()
A=[int(u) for u in A]
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=j-1
        A[j+1]=v
    for u in range(0,N-1):
        print(A[u],end=" ")
    print(A[N-1])

Solution (Python):




n=int(input())
X=list(map(int,input().split()))
curX=[]
for index,i in enumerate(X):
	curX.append(i)
	for j in range(index,0,-1):
		
		if j>0 and curX[j]<curX[j-1]:
			tmp=curX[j-1]
			curX[j-1]=curX[j]
			curX[j]=tmp
	res=curX+X[index+1:]
	print(' '.join(str(e) for e in res))

Solution (Python):

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

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

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

print(NUM_STR)

NUM_LIST = list(map(int, NUM_STR.split()))

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

Solution (Python):


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

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
        print(*A)

insertionSort(A,N)

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

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
def InsertionSort(a,n):
    for i in range(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)
InsertionSort(a,n)

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

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


for k in range(N-1):
    print(a[k],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=j-1
    a[j+1]=v

    for k in range(N-1):
        print(a[k],end=" ")
    
    print(a[N-1])

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


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

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(map(str, A)))

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


a=list(map(int,input().split()))
for k in range(x-1):
    print(a[k],end=' ')
print(a[x-1])


for i in range(1,x):
    j=i-1
    b=a[i]
    
    while j >= 0 and a[j] > b:
        a[j+1]=a[j]
        j=j-1
   
        
    a[j+1]=b
    for k in range(x-1):
        print(a[k],end=' ')
    print(a[x-1])

Solution (Python):
N = int(input())
A = [int(x) for x in 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 = 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())
list = [int(x) for x in input().split()] 
print(*list)

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

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

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

for k in range(n-1):
    print(List[k], end=" ")
print(List[n-1])

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=j-1
    a[j+1]=v
    print(" ".join(map(str,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=j-1
            A[j+1]=v
        print(*A)

N=int(input())

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

print(*A)
insertionSort(A,N)

Solution (Python):
def insertion_sort(Array,num):
    for i in range(1,num):
        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(*A)

n=int(input())
A=[int(i) for i in input().split()]
print(*A)
insertion_sort(A,n)

Solution (Python):
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=j-1
        A[j+1]=v
        print(*A,sep=" ")
N=int(input())
A=list(map(int,input().split()))

insertion_sort(A,N)

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 -= 1

    a[j+1] = key

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

Solution (Python):
def main():
    def insertSort(A):
        N = len(A)
        for i in range(1,N):
            print(*A)
            val = A[i]
            j = i - 1
            while j >= 0 and A[j] > val:
                A[j+1] = A[j]
                j -= 1
            A[j+1] = val
        else:
            print(*A)

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

if __name__ == "__main__":
    main()

Solution (Python):
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        tmp = array[i] 
        if tmp < array[i-1]:
            
            j = i
            while True:
                array[j] = array[j-1]
                j -= 1
                if j == 0 or tmp >= array[j-1]:
                    break
            array[j] = tmp 
        print_list(array)

def print_list(array):
    list_s = [str(x) for x in array]
    print(" ".join(list_s))


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

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

for i in range(1,n):
    print(" ".join(map(str,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(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-=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())
nums = list(map(int, input().split()))
print(" ".join(list(map(str, nums))))
for i in range(1, n):
    for j in range(i):
        if nums[j] > nums[i]:
            nums.insert(j, nums.pop(i))
    print(" ".join(list(map(str, nums))))

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
        print(*A)

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

  else:
    A[j + 1] = v
    for b in range(n):
      print(A[b], end=" \n"[b + 1 == n])

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

        nums[j+1] = v

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


if __name__=="__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    insert_sort(nums, n)

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


def insertionSort(li: list, n: int):
    for i in range(n):
        v = li[i]
        j = i - 1
        while 0 <= j and v < li[j]:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = v
        print(*li)


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

for i in range(1, N+1):
    tmp = S[:i]
    tmp.sort()
    sroted_list = tmp + S[i:]
    str_list =[str(j) for j in sroted_list]
    print(' '.join(str_list))

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    P = list(map(int, input().split()))
    print(' '.join(map(str, P)))
    insertionSort(N, P)


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

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


if __name__ == '__main__':
    main()

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

for i in range(n):
    x=a[i]
    for j in range(i):
        if a[i-j-1]>a[i-j]:
            a[i-j-1],a[i-j]=a[i-j],a[i-j-1]
        else:
            break
    print(" ".join(list(map(str,a))))

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

Solution (Python):
n=int(input())
A = list(map(int,input().split()))
sA=[str(i) for i in A]
pA = ' '.join(sA)
print(pA)
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
    
    sA=[str(i) for i in A]
    pA = ' '.join(sA)
    print(pA)

Solution (Python):

def insertion_sort(arr, num):
    for i in range(1, num):
        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([str(c) for c in a]))


if __name__ == '__main__':
    n = int(input())
    a_str: str = input()
    a = a_str.split(' ')
    a = [int(c) for c in a]
    print(' '.join([str(c) for c in a]))
    insertion_sort(a, n)

Solution (Python):
N = int(input())
A = [int(x) for x in 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
    for _ in range(N):
        if _ == N-1:
            print(A[_],sep='',end='')
        else:
            print(A[_], sep='',end=' ')
    print()

Solution (Python):
n,*a=map(int,open(0).read().split())
for i in range(1,n+1):a[:i]=sorted(a[:i]);print(*a)

Solution (Python):
from sys import stdin

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

li2 = []
for i in range(len(li)):
    s = li.pop(0)
    li2.append(s)
    li2.sort()
    ans = li2+li
    print(' '.join(map(str, ans)))

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 = [int(x) for x in input().split()]

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

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):
        if k == N - 1:
            print(A[k])
        else:
            print(A[k], end=" ")

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A_str=map(str,A)
string=" ".join(A_str)
print(string)
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)
    string=" ".join(A_str)
    print(string)

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

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

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

Solution (Python):
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
        output(a)
    return a


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    insertion_sort(a, n)


def output(int_arr):
    print(" ".join([str(x) for x in int_arr]))


if __name__ == '__main__':
    main()

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


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

def view():
    print(str(a[0]), end = '')
    for k in range(1, n):
        print(' {}'.format(a[k]), end = '')
    print('')
    
for i in range(1, n):
    view()
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = v
view()

Solution (Python):
N = int(input())
s = list(map(int, input().split()))
for k in range(N):
    if k>0:
        print(" ",sep='',end='')
    print(s[k],sep='',end='')
print()



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=j-1

        A[j+1]=v

        
        for k in range(N):
            if k>0:
                print(" ",sep='',end='')
            print(A[k],sep='',end='')

        print()

insertionSort(s,N)

Solution (Python):
def main(n):
	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(map(str,a)))
	return

main(int(input()))

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

if __name__ == "__main__":
    N = int(input())
    A = [int(i) for i in input().strip().split()]
    insertionSort(A, N)

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

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

Solution (Python):
n=int(input())
box=list(map(int,input().split()))
print(*box)
for i in range(1,n):
    while 1:
        if i==0:break
        elif box[i]<box[i-1]:
            box[i],box[i-1]=box[i-1],box[i]
            i -=1
        else:break
    print(*box)

Solution (Python):


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

print(' '.join([str(x) for x in a]))
for i in range(1, len(a)):
    for j in range(i, 0, -1):
        if a[j] < a[j-1]:
            a[j], a[j-1] = a[j-1], a[j]
    print(' '.join([str(x) for x in a]))

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

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

Solution (Python):
N = int(input())
a = [int(i) for i in input().split()]
print(' '.join(map(str, a)))
for i in range(1, N):
    v = a[i]
    j = i - 1
    while j >= 0:
        if a[j] > v:
            a[j + 1], a[j] = a[j], a[j - 1]
            j -= 1
        else:
            break
    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(' '.join(list(map(str, 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(list(map(str, A))))

Solution (Python):
def insertSort(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)

f = insertSort(a, n)

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


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

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

Solution (Python):

def print_result(A, n):
    for i in range(n):
        if i > 0:
            print(' ', end='')
        print(A[i], end='')
    print('\n', end='')


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_result(arr, n)


n = eval(input())

arr = [eval(x) for x in input().split()]
print_result(arr, n)
insertion_sort(arr, n)

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

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


def insertSort(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 -= 1
        A[j + 1] = v
        prList(A)


n = int(input())
A = [int(i) for i in input().split()]
prList(A)
insertSort(A)

Solution (Python):

def main():
    N, *A = map(int, open(0).read().split())
    print(*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(*A)


if __name__ == "__main__":
    main()

Solution (Python):
if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    print(*A)
    for i in range(1, N):
        while(i >= 1 and A[i-1] > A[i]):
            A[i], A[i-1] = A[i-1], A[i]
            i -= 1
        print(*A)

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

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

def printa(A):
  for i in range(N - 1):
    print(A[i] ,end=' ')
  print(A[N - 1],)
  
printa(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
  printa(A)

Solution (Python):
N = int(input())
A =list(map(int,input().split()))
L = [str(a) for a in A]
B = " ".join(L)
print(B)
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
	L = [str(a) for a in A]
	B = " ".join(L)
	print(B)

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

a = [int(x) for x in input().split()]

def plist(a):
    for i in range(len(a)):
        print(a[i],end="")
        if i < len(a)-1:
            print(" ",end="")
    print()
    
plist(a)
for i in range(1,num):
    tmp = a[i]
    j = i - 1
    while (j >= 0 and a[j] > tmp):
        a[j+1] = a[j]
        j -= 1
    a[j+1] = tmp
    plist(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(map(str,A)))
    
    
n = int(input())
test = list(map(int,input().split()))

print(' '.join(map(str,test)))
insertion_sort(test,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):
N=int(input())
nums=list(map(int,input().split()))

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

Solution (Python):
def test():

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

	for k in range(n-1):
		print(f"{A[k]} ",end = '')
	print(f"{A[n-1]}")

	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
		for k in range(n-1):
			print(f"{A[k]} ",end = '')
		print(f"{A[n-1]}")

if __name__ == "__main__":
	test()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
print(*a)
for i in range(1,n):
    num=a[i]
    j=i-1
    while j>=0 and a[j]>num:
        a[j+1]=a[j]
        j-=1
    a[j+1]=num
    print(*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=j-1
        A[j+1]=v
    print(" ".join(map(str,A)))

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

Solution (Python):
def display(l):
    for item in l:
        if not item == l[-1]:
            print(f"{item}", end=' ')
        else:
            print(item)


n = int(input())
lst = list(map(int, input().split()))
display(lst)

for i in range(1, len(lst)):
    key = lst[i]
    j = i - 1
    while j >= 0 and lst[j] > key:
        lst[j+1] = lst[j]
        j -= 1
    lst[j+1] = key
    display(lst)

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())
m = list(map(int, input().split()))
print(*m)
insertion_sort(m,n)

Solution (Python):



n=int(input()) 
A=list(map(int, input().split())) 
print(*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(*A)

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

Solution (Python):
def FUNC00(ARG00):
    for VAR00 in range(1, len(ARG00)):
        VAR01 = ARG00[VAR00]
        VAR02 = VAR00 - 1
        while VAR02 >= 0 and ARG00[VAR02] > VAR01:
            ARG00[VAR02 + 1] = ARG00[VAR02]
            VAR02 -= 1
        ARG00[VAR02 + 1] = VAR01
        print(' '.join([str(VAR03) for VAR03 in ARG00]))
VAR04 = int(input())
VAR05 = [int(VAR06) for VAR06 in input().split()]
print(' '.join([str(VAR06) for VAR06 in VAR05]))
FUNC00(VAR05)

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):
N=int(input())
A=list(map(int,input().split()))
for i in range(len(A)):
    val=A[i]
    j=i-1
    while (j>=0 and A[j]>val):
        A[j+1]=A[j]
        j=j-1
    A[j+1]=val

    string=[str(a) for a in A]
    out=' '.join(string)
    print(out)

Solution (Python):

N = int(input())

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


for i in range(N-1):

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

    i += 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)))

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

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

def insertionSort(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 -= 1
        A[j+1] = v
        pr(A)

pr(A)
insertionSort(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 = j-1
        A[j+1] = v
    for k in range(n-1):
        print(str(A[k]) + " ", end = "")
    print(str(A[n-1]))

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

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

for i in range(1, r):
    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(" ".join(map(str, A)))

Solution (Python):

def printout(array,n):
    output = ""
    for i in range(n-1):
        output += str(array[i]) + " "
    output += str(array[N-1])
    print(output)

N = int(input())
array = [int(i) for i in input().split()]
printout(array,N)

for i in range(1,N):
    a = array[i]
    for j in reversed(range(0,i)):
        if (a < array[j]):
            array[j+1] = array[j]
            array[j] = a
        else:
            break;
    printout(array, N)

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

Input = input()
print(Input)
values = [int(value) for value in Input.split()]

for i in range(1,valuenum):
  for j in range(0,i):
    if values[i] < values[j]:
      values.insert(j, values[i])
      values.pop(i + 1)
      break

  ans = map(lambda value:str(value), values)
  print(' '.join(ans).strip())

Solution (Python):
def insertion_sort(a, n):
    for i in range(n):
        v = a[i]
        j = i-1
        while((j>=0)&(v<a[j])):
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        print(" ".join([str(i) for i in a]))
    return
    
n = int(input())
a = [int(i) for i in input().split()]
insertion_sort(a, n)

Solution (Python):

def InsertionSort(data):
    show(data)
    for i in range(1, len(data)):
        temp = data[i]
        for j in reversed(range(0, i)):
            if data[j] > temp:
                data[j+1] = data[j]
            else:
                data[j+1] = temp
                break
            if j == 0:
                data[0] = temp
        show(data)
    return data

def Input():
    input()
    data = [int(e) for e in input().split()]
    return data

def show(data):
    string = str(data[0])
    for i in range(1, len(data)):
        string = string + " " + str(data[i])
    print(string)

InsertionSort(Input())

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

Solution (Python):
num = int(input())
num_list = input().split(" ")

nums = []

for n in num_list:
    nums.append(int(n))
    
for m in range(num):
    i = nums[m]
    j = m - 1
    while j >= 0 and nums[j] > i:
        nums[j+1] = nums[j]
        j -= 1
    nums[j+1] = i
    
    for n in range(num):
        if n == len(nums)-1:
            print(int(nums[n]), end = "")
            print("")
        else:
            print(int(nums[n]), end = " ")

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


if __name__ == '__main__':
    main()