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

Solution (Python):
N = int(input())
A = [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(' '.join([str(i) for i in A]))

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

Solution (Python):
def Print(numlist):
	for t in range(len(numlist)):
		print(numlist[t], end = '')
		if t != len(numlist) - 1:
			print(end = ' ')
	print()

n = eval(input())
numlist = [eval(item) for item in input().split()]
Print(numlist)
for i in range(1, n):
	tmp = numlist[i]
	for j in range(i, -1, -1):
		if tmp > numlist[j - 1]:
			break
		numlist[j] = numlist[j - 1]
	numlist[j] = tmp
	Print(numlist)

Solution (Python):
def insertion_sort(array):
    print_array(array)
    for i in range(1,len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = key
        print_array(array)

def print_array(array):
     print(str(array)[1:-1].replace(', ', ' '))


def main():
    N = int(input())
    array = [int(s) for s in input().split(' ')]
    insertion_sort(array)

if __name__ == '__main__':
    main()

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

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

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

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

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

Solution (Python):
length = int(input())
targ = [int(n) for n in input().split(' ')]
for l in range(length):
    for m in range(l):
        if targ[l - m] < targ[l - m - 1]:
            disp = targ[l-m -1]
            targ[l-m-1] = targ[l-m]
            targ[l-m] = disp
    print(" ".join([str(n) for n in targ]))

Solution (Python):
length = int(input())
targ = [int(n) for n in input().split(' ')]
for l in range(length):
    insert = 0
    for m in range(l):
        if targ[l] >= targ[l - m - 1]:
            insert = l - m
            break
    aftdisp = targ[l]
    for i in range(0,l - insert):
        disp = targ[l - i]
        targ[l - i] = targ[l - i - 1]
        targ[l - i - 1] = disp
    print(" ".join([str(n) for n in targ]))

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

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

Solution (Python):
_ = input()
A = [int(a) for a in input().split(" ")]
for i in range(1, len(A)):
  print(" ".join([str(a) for a in 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([str(a) for a in A]))

Solution (Python):
def show_list(num_list):
    for i in range(len(num_list)):
        print(str(num_list[i]), end="")
        if i < len(num_list)-1:
            print(" ", end="")
        else:
            print()

input_num = int(input())
num_list = [int(i) for i in input().split()]
show_list(num_list)
for i in range(1, len(num_list)):
    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
    show_list(num_list)

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

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

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(sys.stdin.readline().strip())
    data = [int(i) for i in sys.stdin.readline().strip().split(' ')]
    print_data(data)
    
    for i in range(1, n):
        v = data[i]
        j = i - 1

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

        data[j+1] = v
        print_data(data)
            
if __name__ == '__main__':
    main()

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

Solution (Python):
def insertionSort(_list, _length):
    for i in range(1, _length):
        ll = [str(_l) for _l in _list]
        print(' '.join(ll))
        val = _list[i]
        j = i - 1
        while j >= 0 and _list[j] > val:
            _list[j+1] = _list[j]
            j -= 1
        _list[j+1] = val
    ll = [str(_l) for _l in _list]
    print(' '.join(ll))


length = int(input())
eles = list(map(int, input().split()))

insertionSort(eles, length)

Solution (Python):
length = int(input())
eles = [int(i) for i in input().split()]

for i in range(length):
    val = eles[i]
    j = i - 1
    while j >= 0 and eles[j] > val:
        eles[j+1] = eles[j]
        j -= 1
    eles[j+1] = val
    print(*eles)

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

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

Solution (Python):
def InsertionSort(A , N):
	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 = j -1
		A[j+1] = v 
		print " ".join(map(str, A))

def main():
	N = int( raw_input() )
	A = map(int, raw_input().split())
	print " ".join(map(str, A))
	InsertionSort(A, N)

if __name__=='__main__':
	main()

Solution (Python):

def IS(N,A):
    for i in range(int(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
        ans=""
        for k in range(len(A)):
            ans+=str(A[k])+" "
        print(ans[:-1])

if __name__=="__main__":
    N=input()
    a=input()
    A=a.split(" ")
    for i in range(len(A)):
        A[i]=int(A[i])
    IS(N,A)

Solution (Python):
n = int(raw_input())
A = map(int, raw_input().split(" "))

def printElem(B):
    string = ""
    for elem in B:
        string += str(elem) + " "
    print(string[:len(string)-1])

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

    printElem(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)))
 
if __name__ == "__main__":
    n = int(input())
    a = [int(e) for e in input().split()]
    print(' '.join(map(str, a)))
    insertionSort(a, n)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
print(' '.join([str(A[i]) for i in range(0, N)]))
for i in range(1, N):
    v = int(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[i]) for i in range(0, N)]))

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

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

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

Solution (Python):
num = int(raw_input())
line = raw_input()
 
item_str = line.strip().split(" ")
print " ".join(item_str)
A = map(int, item_str)
 
for i in range(1, num):
    v = A[i]
    j = i - 1
    for j in range(j, -1, -1):
        if A[j] > v:
            A[j+1] = A[j]
            j -= 1
        else:
            break
    A[j+1] = v
    str_A = map(str, A)
    print " ".join(str_A)

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

Solution (Python):



from __future__ import print_function


class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """

    @staticmethod
    def insertion_sort():
        
        array_length = int(input())
        unsorted_array = [int(x) for x in input().split()]

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


if __name__ == '__main__':
    solution = Solution()
    solution.insertion_sort()

Solution (Python):



from __future__ import print_function


class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """

    @staticmethod
    def insertion_sort():
        
        array_length = int(input())
        unsorted_array = [int(x) for x in input().split()]

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


if __name__ == '__main__':
    solution = Solution()
    solution.insertion_sort()

Solution (Python):

N = raw_input()
A =raw_input().split()
print ' '.join(map(str, A)) 
A = map(int, 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 = j - 1 
    A[j+1] = v 
    print ' '.join(map(str,A))

Solution (Python):
def insertionSort(length, numbers):
     for i in range(length):
          for k in range(length):
               if numbers[i] <= numbers[k]:
                    numbers.insert(k, numbers[i])
                    del numbers[i+1]
                    print ' '.join(map(str, numbers))
                    break
          

length = int(raw_input())
numbers = map(int, raw_input().split())


insertionSort(length, numbers)

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

Solution (Python):
N = input()
A = map(int, raw_input().split())
print ' '.join(map(str, A))

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
 
for i in range(1, n):
    print(' '.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):
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(target_list, n_list):
    
    for focus_index in range(1, n_list):
        print(*target_list)
        target = target_list[focus_index]
        if target < target_list[focus_index - 1]:
            compare_index = focus_index

            while compare_index > 0 and target_list[compare_index - 1] > target:
                target_list[compare_index] = target_list[compare_index - 1]
                compare_index -= 1;

            target_list[compare_index] = target
    
    return target_list

def main():
    n_list = int(input())
    target_list = [int(a) for a in input().split()]
    print(*insertion_sort(target_list, n_list))
if __name__ == "__main__":
    main()

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

Solution (Python):
"""
implementation of the Insertion Sort
"""
number_of_input = int(raw_input())

numbers = [int(x) for x in raw_input().split()]

for i in range(1, len(numbers)):
    print " ".join([str(x) for x in numbers])
    target = numbers[i]
    index = i - 1
    while index >= 0 and target < numbers[index]:
        numbers[index + 1] = numbers[index]
        index -= 1
    numbers[index + 1] = target

print " ".join([str(x) for x in numbers])

Solution (Python):
"""
implementation of the Insertion Sort
"""
number_of_input = int(raw_input())

numbers = [int(x) for x in raw_input().split()]

for i in range(1, len(numbers)):
    print " ".join([str(x) for x in numbers])
    target = numbers[i]
    index = i - 1
    while index >= 0 and target < numbers[index]:
        numbers[index + 1] = numbers[index]
        index -= 1
    numbers[index + 1] = target

print " ".join([str(x) for x in numbers])

Solution (Python):
"""
implementation of the Insertion Sort
"""
number_of_input = int(raw_input())

numbers = [int(x) for x in raw_input().split()]
print " ".join([str(x) for x in numbers])
for i in range(1, number_of_input):
    target = numbers[i]
    index = i - 1
    while index >= 0 and target < numbers[index]:
        numbers[index + 1] = numbers[index]
        index -= 1
    numbers[index + 1] = target
    print " ".join([str(x) for x in numbers])

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

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

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

for m in range(N-1):
	print str(A[m]),
print A[N-1]

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

for m in range(N-1):
	print str(A[m]),
print A[N-1]

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

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

insertionSort(A)

Solution (Python):
def insertion_sort(array, debug=False):
    """ AOJ??¬??¶?????¬???
    http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_1_A

    :param array: ?????????????±??????????
    :param debug: ??????????????????????????????????????????????????°
    :return: ?????????????????????
    """
    for i in range(0, len(array)):  
        v = array[i]  
        j = i - 1
        while j >= 0 and array[j] > v:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = v
        if debug is True:
            print(' '.join(map(str, array)))
    return array


if __name__ == '__main__':
    
    
    

    
    num = int(input())
    data = [int(x) for x in input().split(' ')]
    

    
    result = insertion_sort(data, debug=True)

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

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

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

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

Solution (Python):



''' ?????\????????? '''





def insertion_sort(A, N):

    for i in range(N):
        tmp = A[i]
        j = i - 1

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

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

    return A


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

Solution (Python):



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

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

Solution (Python):


def insertion_sort(list):
    for i in range(1, len(list)):
        key = list[i]
        j = i - 1
        show_list(list)
        while(j >= 0 and list[j] > key):
            list[j+1] = list[j]
            j = j - 1
        list[j+1] = key
    show_list(list)
    return list

def show_list(list):
    i = 0;
    while(i < len(list)-1):
        print(list[i], end=" ")
        i = i + 1
    print(list[i])

list_length = int(input())
list = [int(x) for x in input().split(" ")]
insertion_sort(list)

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

n = int(input())
seq = list(map(int, input().split()))
insertion_sort(seq)

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

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


for i in range(N):
    v = card[i]
    j = i - 1
    while j >= 0 and card[j] > v:
        card[j+1] = card[j]
        j = j -1
    card[j+1] = v
    
    card_str = ""
    
    for k in range(N):
        card_str += str(card[k])
        card_str += " "
    
    print(card_str[:-1])

Solution (Python):

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

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

Solution (Python):

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

        
        process_list = map(str, a)
        
        print(" ".join(process_list))


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

insertion_sort(num_array, num_length)

Solution (Python):

n = raw_input()

if n < 1 and n > 100:
	exit()


l = raw_input()

elements = [int(e) for e in l.split()]

print ' '.join(str(e) for e in elements)

for i in range(1, int(n)):
	key = elements[i]
	j = i - 1
	while j >= 0 and elements[j] > key:
		elements[j + 1] = elements[j]
		j -= 1
	elements[j + 1] = key
	
	print ' '.join(str(e) for e in elements)

Solution (Python):



def insertion_sort(seq, l):
    print(' '.join([str(n) for n in seq]))
    for i, v in enumerate(seq[1:], start=1):
        left = i - 1
        while left >= 0 and seq[left] > v:
            seq[left], seq[left+1] = seq[left+1], seq[left]
            left -= 1
        print(' '.join([str(n) for n in seq]))


def to_int(v):
    return int(v)


def to_seq(v):
    return [int(c) for c in v.split()]


if __name__ == '__main__':
    l = to_int(input())
    seq = to_seq(input())

    insertion_sort(seq, l)

Solution (Python):

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



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)

print(*A)
insertion_sort(A, N)

Solution (Python):
debug = True

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

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

print(*arr)
insertionSort(arr, n)

Solution (Python):


import sys

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
    return A

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

for i in range(1,n+1):
    A = insertionSort(A,i)
    for l in range(len(A)):
        if l == len(A)-1:
            print(A[l])
            break
        print(A[l], end=' ')

Solution (Python):

def InsertionSort(A, N):

    print(*A)

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

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

        A[j + 1] = v

        print(*A)

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

InsertionSort(A, N)

Solution (Python):
def insertion(A,n):
  for i in range(0,n):
    tmp = A[i]
    j = i - 1
    while(A[j] > tmp and j >= 0):
      A[j+1] = A[j]
      j-=1
    A[j+1] = tmp
    printList(A)


def printList(A):
  print(" ".join(str(x) for x in A))

n = int(input())
A = [int(x) for x in input().split()]
insertion(A,n)

Solution (Python):
def insertion_sort(target_list):
    sorted_list = list()
    for target in target_list[:]:
        for i, num in enumerate(sorted_list):
            if num > target:
                sorted_list[i:i] = [target]
                break
        else:
            sorted_list.append(target)
        target_list.pop(0)
        print(' '.join(str(s) for s in sorted_list + target_list))

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

Solution (Python):
def insert_sort(A):
    for i in range(1, len(A)):
        k = A[i]
        j = i - 1
        while j >= 0 and A[j] > k:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = k
        show(A)

def show(A):
    for i in range(len(A) - 1):
        print(A[i], end=" ")
    print(A[len(A) - 1])

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

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

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


if __name__ == "__main__":
    import os
    import sys
    if len(sys.argv) > 1:
        if sys.argv[1] == "-d":
            fd = os.open("input.txt", os.O_RDONLY)
            os.dup2(fd, sys.stdin.fileno())
            main()
    else:
        main()

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

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

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

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

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

Solution (Python):
def insertionSort():
    N = int(input())
    lst = list(map(int, input().split()))
    
    for i in range(1, N):
        print(*lst)
        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)
        
insertionSort()

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

for i in xrange(len(a)):
  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())


print " ".join(map(str,a))
for i in xrange(1,len(a)):
  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):
    print (" ".join(map(str,A)))
    for i in range(1,N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        print (" ".join(map(str,A)))

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

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

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

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

for i in range(len(a)):
    for j in range(i):
        if a[i] < a[j]:
            a.insert(j,a.pop(i))
            break
    print(" ".join(map(str,a)),)

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

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

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

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


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

Solution (Python):
def rren(): return list(map(int, input().split()))
N = int(input())
R = rren()

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

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

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

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

Solution (Python):
num_cnt = int(input().rstrip())

nums = list(map(int, input().rstrip().split(" ")))

for i in range(num_cnt):
    tmpNum = nums[i]
    j = i -1 
    
    while j >=0:
        if nums[j] <= tmpNum:
            break
        nums[j+1] = nums[j]
        j = j-1
    nums[j+1] = tmpNum
    print (" ".join(map(str,nums)))

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

def trace(A):
    for index, v in enumerate(A):
        print(v, end='')
        if index != len(A) - 1:
            print(' ', end='')
    print()

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