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


if __name__ == '__main__':
    main()

Solution (Python):
def insertingSort(a, 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(' '.join(list(map(str, a))))        

n = int(input().strip())
a = list(map(int, input().strip().split()))
print(' '.join(list(map(str, a))))
insertingSort(a, n)

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

Solution (Python):

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

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

pr = str(a[0])
for i in range(n-1):
    i = i + 1
    pr += " " + str(a[i])
print(pr)

insertion_sort(a, n)

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

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

def p(a, n):
  for i in range(n):
    if i==n-1: 
      print(a[i],end='')
    else :
      print(a[i], end=' ')

def f(a, n):
  for i in range(n):
    v = a[i]
    j = i-1
    while (a[j] > v) & (j>=0):
      a[j+1] = a[j]
      j-=1
    a[j+1] = v
    p(a, n)
    print()
f(a, n)

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

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

insertSort(A,N)

Solution (Python):
from sys import stdin


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)

if __name__ == "__main__":
    N = int(stdin.readline())
    A = [int(item) for item in stdin.readline().split()]
    
    insertionSort(A, N)

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


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


if __name__ == '__main__':
    main()

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

for i, a in enumerate(A):
    j = i - 1
    while j >= 0 and a < A[j]:
        A[j + 1] = A[j]
        j -= 1
    else:
        A[j + 1] = a
        print(*A)

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

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

    print(*a)

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

for i in range(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([str(x) for x in arr]))

Solution (Python):
def insert_sort(A):
    a = list(A)
    print(' '.join(map(str, a)))
    for move_index in range(1, len(a)):
        compare_index = move_index -1
        while compare_index >= 0 and a[compare_index] > a[move_index]:
            a[compare_index], a[move_index] = int(a[move_index]), int(a[compare_index])
            compare_index -= 1
            move_index -= 1
        print(' '.join(map(str, a)))
    return a

input()
A = list(map(int, input().split()))
insert_sort(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 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:list, n:int):
    for i in range(0,n):
        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)))
    return a

def main():
    n = int(input())
    a = list(map(int, input().split()))
    InsertionSort(a, n)


if __name__ == "__main__":
    main()

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

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

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

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

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

Solution (Python):
def print_list(a):
    out = ''
    for ai in a:
        out += str(ai) + ' '
    else:
        out = out[:-1]
    print(out)

def insertion_sort(n, a):
    for i in range(1, n):
        print_list(a)
        v = a[i]
        sorted_list_idx = i
        while sorted_list_idx > 0 and a[sorted_list_idx - 1] > v:
            a[sorted_list_idx] = a[sorted_list_idx - 1]
            sorted_list_idx -= 1
        a[sorted_list_idx] = v
    return a


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

a = insertion_sort(n, a)

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

N = int(input())
A = list(map(int, input().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 -= 1
        a[j + 1] = v
        print(*a)


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

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

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

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

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

print(*working_list)

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

Solution (Python):
n = input()
b = int(n) - 1

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


for j in range(int(n)):
	if j != 0:
		for c2 in reversed(range(0,j)):
			if nlist[c2] > nlist[j]:
				stk = nlist[c2]
				nlist[c2] = nlist[j]
				nlist[j] = stk
				j = j - 1
				c2 = j - 1


	for i in range(int(b)):
		print(nlist[i], end=" ")

	print(nlist[b])

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
        for j in range(0,N-1):
            print("{0} ".format(A[j]),end = '')
        print(A[N-1])


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

for i in range(0,N-1):
    print("{0} ".format(A[i]),end = '')
print(A[N-1])

InsertionSort(A,N)

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

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

Solution (Python):
def main():
    
    n = int(input())
    a = input().split()
    
    A = []
    for i in range(n):
        A.append(int(a[i]))
        
    display(A)
    insertSort(A)
        
def insertSort(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
        display(A)
            
def display(A):
    for i in range(len(A)):
        if i != len(A) - 1:
            endStr = ' '
        else:
            endStr = '\n'
        print(str(A[i]), end=endStr)
                
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
    b = [str(n) for n in a]
    print(" ".join(b))

Solution (Python):
n = int(input())
A = input().split()

print(' '.join(A))
for i in range(1,n):
    for j in range(i,0,-1):
        if int(A[j]) < int(A[j-1]):
            A[j], A[j-1] = A[j-1], A[j]
    print(' '.join(A))

Solution (Python):
def main():
    
    num = int(input())
    a = list(int(i) for i in input().split())

    print(*a)
    insertSort(a)

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

if __name__ == "__main__":
    main()

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

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


print(" ".join([str(i) for i in 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(" ".join([str(i) for i in 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())
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):
num = int(input())
list = list(map(int, input().split()))

for i in range(num):
    v = list[i]
    if i == 0:
        list[0] = v
    else:
        j = i - 1
        while j >= 0 and list[j] > v:
            list[j+1] = list[j]
            j -= 1
        list[j+1] = v

    result = ''
    for i in range(num):
        result += str(list[i]) + ' '

    print(result[:-1])

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

Solution (Python):
N = int(input())
A = [int(n) for n in 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 insertSort(li,num):
	for i in range(1,num):
		j = i
		while li[j] < li[j-1] and j > 0 :
			tmp = li[j]
			li[j] = li[j-1]
			li[j-1] = tmp
			j -=1

		for k in range(len(li)):
			if k != len(li)-1:
				print(li[k],"",end="")
			else:
				print(li[k])

if __name__ == '__main__':
	num = int(input())
	li = list(map(int,input().split()))

	for i in range(len(li)):
		if i != len(li)-1:
			print(li[i],"",end="")
		else:
			print(li[i])

	insertSort(li,num)

Solution (Python):
def InsertSort(A, N): 
    str_A = map(str, A)
    print(" ".join(str_A))
    for i in range(N - 1):
        for j in range(i + 1):
            if A[i + 1 - j] < A[i - j]:
                A[i + 1 - j], A[i - j] = A[i - j], A[i + 1 - j]
            else:
                pass
        str_A = map(str, A)
        print(' '.join(str_A))


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

InsertSort(a, n)

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

def allprint(a, n):
  for i in range(n):
    if i > 0:
      print(" ",end="")
    print(a[i],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 -= 1
    a[j + 1] = v
    allprint(a,n)

allprint(a,n)
insertionSort(a,n)

Solution (Python):
N = int(input())
A = [i for i in 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 ALDS1_1_A():
    """
    1 insertionSort(A, N) // N個の要素を含む0-オリジンの配列A
    2   for i が 1 から N-1 まで
    3     v = A[i]
    4     j = i - 1
    5     while j >= 0 かつ A[j] > v
    6       A[j+1] = A[j]
    7       j--
    8     A[j+1] = v

    ＜問題＞
    N 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムを作成してください。
    上の疑似コードに従いアルゴリズムを実装してください。アルゴリズムの動作を確認するため、
    各計算ステップでの配列（入力直後の並びと、各 i の処理が終了した直後の並び）を出力してください。

    ＜入力＞
    入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。

    ＜出力＞
    出力は N 行からなります。挿入ソートの各計算ステップでの途中結果を 1 行に出力してください。
    配列の要素は１つの空白で区切って出力してください。最後の要素の後の空白など、余計な空白や改行を含めると
    Presentation Error となりますので注意してください。

    ＜制約＞
    1 ≤ N ≤ 100
    0 ≤ A の要素 ≤ 1,000
    """
    N = int(input())
    A = [int(e) for e in 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)))


def main():
    ALDS1_1_A()


if __name__ == '__main__':
    main()

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 insertion_sort(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)))


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

Solution (Python):
N, *A = map(int, open(0).read().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):
def output_A(A):
    if len(A) == 1:
        print(A[0])
    else:
        for i in range(len(A)-1):
            print(f'{A[i]} ',end="")
        print(f'{A[i+1]}',)

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

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

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


def main():
    sc = Scan()
    n = sc.intarr()[0]
    array = sc.intarr()

    for i in array:
        if i == array[-1]:
            print(i, end='')
        else:
            print(i, end=' ')
    print("")

    for i in range(1, n):
        v = array[i]
        j = i - 1

        while j >= 0 and array[j] > v:
            array[j+1] = array[j]
            j = j - 1
        array[j+1] = v
        for i in array:
            if i == array[-1]:
                print(i, end='')
            else:
                print(i, end=' ')
        print("")


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()

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
            
            for k in range(N-1):
                print(str(A[k]), end = " ")
            print(A[N-1])

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

 

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

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

print(" ".join(map(str, 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]
    insert_index = i
    for j in reversed(range(i)):
        if A[j] > V:
            insert_index = j
    A.pop(i)
    A.insert(insert_index, V)
    print(*A)

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

for i in range(n):
  v =A[i]
  j=i-1
  while (j>=0)&(A[j]>v):
    
    
    A[j+1]=A[j]
    A[j] = v
    j-=1
  print(*A, sep=' ')

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    for i in range(n):
        a = aa.pop(i)
        for j in range(i - 1, -1, -1):
            if aa[j] <= a:
                aa.insert(j + 1, a)
                break
        else:
            aa = [a] + aa
        print(*aa)

main()

Solution (Python):
def main():
    n = int(raw_input().strip())
    data = map(int, raw_input().split())
    print " ".join([str(x) for x in data])
    insertion_sort(n, data)

def insertion_sort(n, data):
    for i in xrange(1, n):
        if data[i - 1] > data[i]:
            temp = data[i]
            while i > 0 and data[i - 1] > temp:
                data[i] = data[i - 1]
                i -= 1
            data[i] = temp
        print " ".join([str(x) for x in data])

if __name__ == '__main__':
    main()

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

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

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

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

Solution (Python):
n = int(input())
l = list(map(int,input().split()))
def insertionSort(l,n):
    ans = map(str,l)
    print(" ".join(ans))
    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
        ans = map(str,l)
        print(" ".join(ans))
insertionSort(l,n)

Solution (Python):
N = int(input())
A = [int(i) for i 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 -= 1
    
    A[j+1] = v
    print(*A)

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


def main():
    num = int(input())
    array = input()
    array = list(map(int, array.split()))
    insertion_sort(array, num)
    


if __name__ == "__main__":
    main()

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

def trace(numbers):
  a = str(numbers[0])
  for i in range(1,len(numbers)):
    a += " "
    a += str(numbers[i])
  print(a)

trace(numbers)
for current_i in range(1,N):
  for compare_i in range(current_i-1,-1,-1):

    if(numbers[compare_i] > numbers[current_i]):
      hoge = numbers[compare_i]
      numbers[compare_i] = numbers[current_i]
      numbers[current_i] = hoge

      current_i = compare_i
  trace(numbers)

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 insertion_sort(A):
    print(*A)
    for j in range(1,len(A)):
        key=A[j]
        i=j-1
        while i>=0 and A[i]>key:
            A[i+1]=A[i]
            i=i-1
        A[i+1]=key
        print(*A)
    return A

insertion_sort(A)

Solution (Python):



def insertion_sort(a, n):
    for i in range(1, n):
        print(*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)

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

insertion_sort(a, n)

Solution (Python):
n=int(input())
l=list(map(int, input().split()))
for i in range(n):
    if i!=n:
        part_l=sorted(l[0:i+1])  
        l=part_l+l[i+1:n+1]
        print(*l)

    elif i==n:
        if l[i-1]>l[i]:
            l=+list(reversed(l[i-1:i]))
            print(*l)

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

Solution (Python):

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


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

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

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

Solution (Python):
n = int(input())
a = [int(i) for i 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
	print(*a)

Solution (Python):
L, A = int(input()), input()
print(A)

A = [int(i) for i in A.split()]
for i in range(1, L):
    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(k) for k in A]
    l = ' '.join(l)
    print(l)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
A_str = [str(a) for a in A]
print(" ".join(A_str))

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

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

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=list(map(int,input().split()))
B=list(map(str,A))
print(' '.join(B))
for i in range(1,N):
    v=A[i]
    j=i-1
    while j!=-1 and A[j]>v:
        A[j+1]=A[j]
        j-=1
    A[j+1]=v
    B=list(map(str,A))
    print(' '.join(B))

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
    for j in range(len(A)-1):
        print(A[j],end=" ")
    print(A[-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 -= 1
    a[j+1] = v
    print(' '.join(map(str,a)))

Solution (Python):
def print_list(numlist):
    n = len(numlist)
    for i in range(n):
        if i == n - 1:
            print(numlist[i])
        else:
            print(numlist[i], end=' ')
        
if __name__ == '__main__':
    n = int(input())
    numlist = [int(num) for num in input().split(' ')]
    
    print_list(numlist)
    for i in range(1, n):
        key_value = numlist[i]
        j = i - 1
        while j >= 0 and numlist[j] > key_value:
            numlist[j + 1] = numlist[j]
            j -= 1
        numlist[j + 1] = key_value
        print_list(numlist)

Solution (Python):
n = int(input())
list1 = list(map(int,input().split()))
for i in range(0,n):
    v = list1[i]
    for j in range(i,-1,-1):
        if list1[j] > v:
            tmp = list1[j]
            list1[j] = v
            list1[j+1] = tmp
            
    for m in range(n):
        if m == n-1:
            print(list1[m])
        else:
            print(list1[m],end=' ')

Solution (Python):

import functools


def pretty_print(arr: [int]):
    return functools.reduce(lambda a, b: f'{a} {b}', arr)


def custom_sort(arr: [int]):
    print(pretty_print(arr))
    for i in range(1, len(arr)):
        val = arr[i]
        
        j = i - 1
        
        while j >= 0 and arr[j] > val:
            
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = val
        print(pretty_print(arr))
    return arr


length = input()
array: [int] = list(map(lambda n: int(n), input().split(' ')))


custom_sort(array)

Solution (Python):
import sys

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

for i in range(1, n):
    print(' '.join(list(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(list(map(str, a))))

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

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    print_arr(arr)
    for i in range(1, len(arr)):
        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_arr(arr)

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

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

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

def print_output(_list):
    for index in range(len(_list)):
        if index == len(_list) - 1:
            print(_list[index])
        else:
            print(_list[index],end=' ')

target_length = int(input())
target_list = list(map(int,input().split()))
print_output(target_list)
for index in range(1, target_length):
    v = target_list[index]
    j = index -1
    while (j >= 0 and target_list[j] > v):
        target_list[j + 1] = target_list[j]
        j -= 1
    target_list[j + 1] = v
    print_output(target_list)

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

print(*a)
insertionSort(a,n)

Solution (Python):
n = int(input())
a = [int(i) for i in 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)))