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 intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def show(a):
    
    _str = ""
    for i in range(len(a) - 1): _str += str(a[i]) + " "
    _str += str(a[len(a) - 1])
    print(_str)

def main():
    n = int(input())
    a = intinput()
    
    for i in range(n):
        
        
        cur = i
        while cur > 0:
            if a[cur - 1] > a[cur]:
                a[cur - 1], a[cur] = a[cur], a[cur - 1]
            else: break
            cur -= 1
        show(a)

if __name__ == "__main__":
    main()

Solution (Python):


def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def show(a):
    
    _str = ""
    for i in range(len(a) - 1): _str += str(a[i]) + " "
    _str += str(a[len(a) - 1])
    print(_str)

def main():
    n = int(input())
    a = intinput()
    
    for i in range(n):
        
        
        cur = i
        while cur > 0:
            if a[cur - 1] > a[cur]:
                a[cur - 1], a[cur] = a[cur], a[cur - 1]
            else: break
            cur -= 1
        show(a)

if __name__ == "__main__":
    main()

Solution (Python):

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

B = " ".join([str(num) for num in A])
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] = A[j], A[j+1]
        j -= 1
        
    B = " ".join([str(num) for num in A])
    print(B)

Solution (Python):
def print_A():
    for i, n in enumerate(A):
        if i == N - 1:
            print(n)
        else:
            print(n, end=' ')

def insert():
    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()
insert()

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_list_split_whitespace(a)


def print_list_split_whitespace(a):
    for x in a[:-1]:
        print(x, end=' ')
    print(a[-1])


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

print_list_split_whitespace(a)
insertion_sort(a, n)

Solution (Python):
n = int(input())
x = input().split()
y=[]
for i in range(n):
    y += [int(x[i])]
for i in range(n-1):
    print(y[i],end=' ')
print(y[n-1])

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

Solution (Python):
def trace(A, N):
    print(*A)

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
        trace(A, N)


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

Solution (Python):



if __name__ == '__main__':
    raw_input()
    l = map(int, raw_input().split())
    for i in range(1, len(l)):
        print ' '.join(map(str, l))
        v = l[i]
        j = i - 1
        while j >= 0 and l[j] > v:
            l[j + 1] = l[j]
            j -= 1
        l[j + 1] = v
    print ' '.join(map(str, l))

Solution (Python):
def print_list(array, N):
    for i, e in enumerate(array):
        if i == N - 1:
            print(e)
        else:
            print(e, end=" ")

N = int(input())
a = [int(e) for e in input().split()]
print_list(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_list(a, N)

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):
from sys import stdin
def stdinput():
    return stdin.readline().strip()

def main():
    n = int(stdinput())
    a = list(map(int, stdinput().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)))

if __name__ == '__main__':
    main()

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

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

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

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

def print_arr(arr):
	for i in range(len(arr)):
		sys.stdout.write(str(arr[i]))
		if i != len(arr) - 1:
			sys.stdout.write(' ')
	print()

for i in range(n):
	key = arr[i]
	j = i - 1
	while j >= 0 and arr[j] > key:
		arr[j + 1] = arr[j]
		j = j - 1
	arr[j + 1] = key
	print_arr(arr)

Solution (Python):
import sys

def print_arr(arr):
	for i in range(len(arr)):
		sys.stdout.write(str(arr[i]))
		if i != len(arr) - 1:
			sys.stdout.write(' ')
	print()

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

for i in range(n):
	key = arr[i]
	j = i - 1
	while j >= 0 and arr[j] > key:
		arr[j + 1] = arr[j]
		j = j - 1
	arr[j + 1] = key
	print_arr(arr)

Solution (Python):
import sys
n = input()
data = map(int, raw_input().split())
for i in range(1,n):
	for k in range(0,n-1):
		sys.stdout.write(str(data[k])+" ")
	sys.stdout.write(str(data[n-1]))
	print
	temp = data[i]
	j = i-1
	while j >= 0 and data[j] > temp:
		data[j+1] = data[j]
		j = j - 1
		data[j+1] = temp
for k in range(0,n-1):
	sys.stdout.write(str(data[k])+" ")
sys.stdout.write(str(data[n-1]))
print

Solution (Python):
import sys
def print_arr(arr):
	for i in range(len(arr)):
		sys.stdout.write(str(arr[i]))
		if i != len(arr) - 1:
			sys.stdout.write(' ')
	print()

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

for i in range(n):
	key = arr[i]
	j = i - 1
	while j >= 0 and arr[j] > key:
		arr[j + 1] = arr[j]
		j -= 1
	arr[j + 1] = key
	print_arr(arr)

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

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

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

if __name__ == '__main__':
    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=input().split()
for i in range(n):
 k=int(a[i])
 j=i-1
 while j>=0 and int(a[j])>k:
  a[j+1]=a[j]
  j-=1
 a[j+1]=k
 print(*a)

Solution (Python):
N = int(input())
arr = [int(n) for n in 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())
arr = [int(n) for n in 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):
import sys

def print_arr(arr):
	for i in range(len(arr)):
		sys.stdout.write(str(arr[i]))
		if i != len(arr) - 1:
			sys.stdout.write(' ')
	print()

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

for i in range(n):
	key = arr[i]
	j = i - 1
	while j >= 0 and arr[j] > key:
		arr[j + 1] = arr[j]
		j -= 1
	arr[j + 1] = key
	print_arr(arr)

Solution (Python):
def insertionSort(A,N):
    print(' '.join([str(a) for a 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(a) for a in A]))

def run():
    N = int(input())
    A = [int(i) for i in input().split()]
    insertionSort(A,N)

if __name__ == '__main__':
    run()

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

if __name__ == '__main__':
    print(" ".join(map(str, A)))
    for i in range(1, N):
        target_num = A[i]
        for j in range(i):
            if A[j] > target_num:
                tmp_idx = i
                while j < tmp_idx:
                    A[tmp_idx] = A[tmp_idx-1]
                    tmp_idx -= 1
                A[j] = target_num
                break
        print(" ".join(map(str, A)))

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

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

Solution (Python):


n = int(input())
integers = [int(i) for i in input().rstrip().split()]

def show(a):
    for i in range(len(a)):
        if i < len(a) - 1:
            print(a[i], end = ' ')
    return a[len(a) - 1]

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

print(insertionSort(integers, n))

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

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

    insertionSort(A, N)

main()

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


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

insertionSort(a)

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

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

for i in range(len(arr)):
    for j in range(i,0,-1):
        if(arr[j] < arr[j-1]):
            temp = arr[j]
            arr[j] = arr[j-1]
            arr[j-1] = temp
        else:
            continue
    print(' '.join(map(str,arr)))

Solution (Python):



def insertionSort(A, N):
    """N個の要素を含む0-オリジンの配列A"""
    print(' '.join(map(str, A)))
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        print(' '.join(map(str, A)))

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

insertionSort(A, N)

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


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

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

Solution (Python):
def main():
    N = int(raw_input())
    A = map(int, raw_input().split())
    sort(A)

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

def display(A):
    print(" ".join(map(str, A)))

main()

Solution (Python):
def trace(x):
    for e in x:
        print e,
    print

n = input()
x = map(int, raw_input().split())
trace(x)

for j in range(1, n):
    key = x[j]
    for i in range(j)[::-1]:
        if x[i] > key:
            x[i+1] = x[i]
        else:
            i += 1
            break
    else:
        i = 0
    x[i] = key
    trace(x)

Solution (Python):

from __future__ import division, print_function
from sys import stdin
stdin.readline()
ar = [int(s) for s in stdin.readline().split()]
print(*ar)
for j in range(1, len(ar)):
    key = ar[j]
    i = j - 1
    while i >= 0 and ar[i] > key:
        ar[i+1] = ar[i]
        i -= 1
    ar[i+1] = key
    print(*ar)

Solution (Python):



import time
import sys
import io
import re
import math

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

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

Solution (Python):
n = int(raw_input())
A = map(int,raw_input().split())
print " ".join(map(str,A))
for j in range(1,n):
    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 " ".join(map(str,A))

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

Solution (Python):
n = int(raw_input())
a = map(int, raw_input().split())
print " ".join(map(str, a))
for j in range(1,n):
    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 " ".join(map(str, a))

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

n = int(raw_input())
a = map(int, raw_input().split())
isort(n,a)

Solution (Python):
def isort(n,a):
    p(a)
    for j in range(1,n):
        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
        p(a)

def p(a):
    print " ".join(map(str, a))

n = int(raw_input())
a = map(int, raw_input().split())
isort(n,a)

Solution (Python):
n = int(raw_input())
a = map(int, raw_input().split())
print " ".join(map(str, 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 " ".join(map(str, a))

Solution (Python):
def insertion_sort(A, N):
    for j in range(1, N):
        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 " ".join(map(str, A))

if __name__ == "__main__":
    import sys
    N = int(sys.stdin.readline().strip())
    A = [ int(e) for e in sys.stdin.readline().strip().split() ]
    print " ".join(map(str, A))
    insertion_sort(A, N)

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

for i in range(1, len(a)):
    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):
num = int(input())
number_list = list(map(int, input().split(" ")))


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

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

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

for j in range(n):
    if j<n-1:
      print(a[j],end=" ")
    else:
      print(a[j])
      
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 j in range(n):
    if j<n-1:
      print(a[j],end=" ")
    else:
      print(a[j])

Solution (Python):
def insertion_sort(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] = a[j], a[j+1]
            j -= 1
        print(*a)

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

insertion_sort(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
        print(*A)
        
if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(*A)
    insertionSort(A, N)

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

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

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

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


def insertionSort(a:list, n:int):
    for i in range(1, n):
        now = a[i] 
        j = i - 1 
        while j >= 0 and a[j] > now: 
            
            a[j+1] = a[j]
            
            j -= 1
        
        a[j + 1] = now
        output(a)
output(a)       
insertionSort(a, n)

Solution (Python):
n = int(input())
a = input().split()
for s in range(len(a)-1):
        print(a[s],end=' ')
print(a[-1])
for i in range(1,n):
    x = int(a[i])
    j = i-1
    while j >=0 and int(a[j])>x:
        t = int(a[j])
        r = int(a[j+1])
        a[j+1] = t
        a[j] = r
        j -=1
    s = 0
    for s in range(len(a)-1):
        print(int(a[s]),end=' ')
    print(int(a[-1]))

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

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

    for j in range(i-1,-1,-1):
        if (A[j] > v):
            A[j+1] = A[j]
            A[j] = v

        else :
            break

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

Solution (Python):
num = int(input())
num_list = list(map(int, input().split(" ")))
for x in range(len(num_list)):
    if x == len(num_list) - 1:
        print(num_list[x])
    else:
        print(num_list[x],end=" ")

for i in range(1, num):
    v = num_list[i]
    j = i - 1
    while j >= 0 and num_list[j] > v:
        num_list[j + 1] = num_list[j]
        j -= 1
        num_list[j + 1] = v
    for x in range(len(num_list)):
        if x == len(num_list) - 1:
            print(num_list[x])
        else:
            print(num_list[x],end=" ")

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
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([str(x) for x 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(x) for x in a]))

Solution (Python):
def main():
    n = int(input())
    nums = input()
    print(nums)
    nums = nums.split(' ')
    nums = [int(i) for i in nums]
    insertion_sort(n, nums)


def insertion_sort(n, 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__":
    main()

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

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

def insertionSort(A,N):
    print(" ".join(map(str,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(map(str,A)))
    return A

lst2 = insertionSort(lst,N)

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

for i in range(N):
    if i==N-1:
        print(S[i])
    else:
        print(S[i],end=' ')

for i in range(1,N):
    key = S[i]
    if key < max(S[0:i]):
        S.pop(i)
        x = 0
        for k in range(i):
            if x==1:
                continue
            if key < S[k]:
                S.insert(k,key)
                x += 1
    
    for k in range(N):
        if k==N-1:
            print(S[k])
        else:
            print(S[k],end=' ')

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

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

print(' '.join(str(x) for x in L))

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


print(" ".join([str(a) for a 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(a) for a in A]))

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

def show_step(A):
    ans = str(A[0])
    for a in A[1:]:
        ans += " "+str(a)
    print(ans)

show_step(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_step(A)

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

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

for i in range(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
    print(' '.join(map(str, nums)))

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

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

Solution (Python):
import sys

def print_data(data):
    last_index = len(data) - 1
    
    for idx, item in enumerate(data):
        print(item, end='')
        if idx != last_index:
            print(' ', end='')

    print('')
        
def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    nowmax = -1
    result = []
    for i in range(N):
        if A_list[i] >= nowmax:
            result.append(A_list[i])
            nowmax = A_list[i]
        else:
            junban = []
            for j in range(i):
                if A_list[i] < result[j]:
                    asa = result[:j]
                    junban = asa
                    junban.append(A_list[i])
                    junban += result[j:]
                    result = junban
                    break         
        shutu = result[:i+1] + A_list[i+1:]
        print_data(shutu)
            
if __name__ == '__main__':
    main()

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

print(str(A).replace('[', '').replace(']', '').replace(',', ''))

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(str(A).replace('[', '').replace(']', '').replace(',', ''))

Solution (Python):
N = int(input())
a = list(map(int, 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([str(x) for x in a]))

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

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

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

for i in range(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(*lst)

Solution (Python):
a= int(input())
x =[int(z) for y, z in enumerate(input().split()) if y < a and z.isdigit()]
print(*x)
for i in range(1,a):
    key = x[i]
    j = i-1
    while j >= 0 and x[j] > key:
        x[j+1] = x[j]
        j -= 1
    x[j+1] = key
    print(*x)

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

def show(A):
    for t in range(len(A)):
        if t != N -1:
            print(number[t],'',end='')
        else:
            print(number[t])


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

show(number)

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

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

Solution (Python):
def print_list(nums):
    output = ""
    for i in nums:
        output += str(i) + ' '
    print(output[:-1])

from sys import stdin
N = int(input())
nums = list(map(lambda x:int(x), stdin.readline().split(' ')))
for i in range(1, N):
    print_list(nums)
    num = nums[i]
    for j in range(0, i):
        if nums[j] > num:
            nums.insert(j, num)
            del nums[i+1]
            break
print_list(nums)

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

for i in range(len(A)):
    while i > 0:
        if A[i] < A[i-1]:
            A[i], A[i-1] = A[i-1], A[i]
            i -= 1
        else:
            break
    print (" ".join([str(v) for v in A]))

Solution (Python):



def insert_sort(arr):
    for index in range(1, len(arr)):
        insert(index, arr)

def insert(index, arr):
    tmp = arr[index]
    for i in range(index-1, -1, -1):
        if arr[i] > tmp:
            arr[i + 1] = arr[i]
            arr[i] = tmp
        else:
            arr[i + 1] = tmp
            break
    print(" ".join(map(str, arr)))

n = input()

l = list(map(int, input().split()))
print(" ".join(map(str, l)))
insert_sort(l)

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

print(' '.join(list(map(str, a))))
for i in range(1, n):
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = key
    print(' '.join(list(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):
            c=A[j+1]
            A[j+1]=A[j]
            A[j]=c
            j-=1
        for i in range(len(A)):
            if i!=len(A)-1:
                print(A[i],end=" ")
            else:
                print(A[i])                
a=int(input())
b=list(map(int,input().split()))
for i in range(len(b)):
    if i!=len(b)-1:
        print(b[i],end=" ")
    else:
        print(b[i])   
insertionSort(b,a)

Solution (Python):
num = int(input())
list = list(map(int,input().split()))
list_str = []
for i in list:
    list_str.append(str(i))

print(" ".join(list_str))
for i in range(1,num):
    v = list[i]
    j = i - 1
    while j>= 0 and list[j]>v:
        list[j+1] = list[j]
        j -= 1
    list[j+1] = v
    list_str = []
    for i in list:
        list_str.append(str(i))
    print(" ".join(list_str))