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 = 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 index, value in enumerate(A):
    if index == 0:
        continue

    prev_idx = index - 1
    while prev_idx >= 0 and A[prev_idx] > value:
        A[prev_idx + 1] = A[prev_idx]
        prev_idx -= 1
    A[prev_idx + 1] = value
    trace(A)

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

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

sort(line)

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

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
print(*A)
for i in range(1, len(A)):
    key = A[i]
    j = i-1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j += -1
        A[j+1] = key
    print(*A)

Solution (Python):
def insertion_sort(array, element_number):
    for i in range(element_number):
        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 k in range(element_number):
            if k < element_number-1:
                print(str(array[k]) + ' ', end='')
            else:
                print(str(array[k]), end='')

        print('\n', end='')

def test():
    element_number = int(input())
    input_array = list(map(int, input().split()))

    insertion_sort(input_array, element_number)

if __name__ == '__main__':
    test()

Solution (Python):
def insertion_sort(array):
    '''?????????????´?????????????????????¨??????????????????????????¨???????????????????????§?????\?????????????????°????????????
    1. ??????????????¨??????????????????????´?????????????????????? v ????¨?????????????
    2. ????????????????????¨??????????????????v ????????§??????????´??????????????????????????§?????????????
    3. ?????????????????????????????????????????????????´? v???????????\?????????'''

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

def test():
    '''??? input =
    6
    5 2 4 6 1 3
    ->
    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'''
    
    element_number = int(input())
    input_array = list(map(int, input().split()))

    insertion_sort(input_array)

if __name__ == '__main__':
    test()

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

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

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

insertionSort(a,n)

Solution (Python):
import sys


def print_arr(arr):
    ln = ''
    for v in arr:
        ln += str(v) + ' '

    ln = ln.strip()
    print(ln)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        print_arr(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)

input0 = sys.stdin.readline()
input_sample = sys.stdin.readline()

input = input_sample.split(" ")
input = [int(i) for i in input]
insertion_sort(input)

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

for i in range(1, N):
    print(" ".join([str(x) for x in 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(x) for x in A]))

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

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

    InsertionSort(N, A)

def InsertionSort(N, A):
    print(*A)
    for i in range(1, N):
        v = A[i]
        for j in range(i - 1, -1, -1):
            if A[j] > v:
                A[j + 1] = A[j]
            else:
                A[j + 1] = v
                break
        else:
            A[0] = v

        print(*A)

if __name__ == '__main__':
    solve()

Solution (Python):


import sys
import os



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

        
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        print(*A)

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

Solution (Python):
def get_input():
    length = int(raw_input())
    return map(int, raw_input().split())


def insertionSort(input_array):
    print " ".join(str(each)  for each in input_array).rstrip(" ")
    for i in range(1,len(input_array)):
        key = input_array[i]
        j = i-1
        while j >= 0 and input_array[j] > key:
            input_array[j+1] = input_array[j]
            j -= 1
            input_array[j+1] = key
        print " ".join(str(each)  for each in input_array).rstrip(" ")

insertionSort(get_input())

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

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

result_list = []
result_list.append(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
    result_list.append(A[:])

for i in range(n):
    if i > len(result_list):
        print(' '.join(str(n) for n in result_list[-1]))
    print(' '.join(str(n) for n in result_list[i]))

Solution (Python):

size = int(input())
line = list(map(int, input().split()))

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

def main():
    insertionSort(line, size)

if __name__ == '__main__':
    main()

Solution (Python):
def isort(seq, n):
    for i in range(1, n):
        x = seq[i]
        j = i - 1
        while j >= 0 and seq[j] > x:
            seq[j + 1] = seq[j]
            j -= 1
        seq[j + 1] = x
        print(*seq)


n = int(input())

x = list(map(int, input().split()))
print(*x)
isort(x, n)

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

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

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

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

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

Solution (Python):
def print_list(ele_list):
    print(" ".join(map(str, ele_list)))

def insertion_sort(ele_list):
    len_ele_list = len(ele_list)
    print_list(ele_list)
    for i in range(1, len_ele_list):
        key = ele_list[i]
        j = i - 1
        while j >= 0 and ele_list[j] > key:
            ele_list[j+1] = ele_list[j]
            j -= 1
        ele_list[j+1] = key
        print_list(ele_list)

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

insertion_sort(ele_list)

Solution (Python):


N = int(input())

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

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

Solution (Python):
size = int(input())
element = list(map(int,input().split()))
print(" ".join(map(str,element)))


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

Solution (Python):


def printls(ls):
    print(' '.join(map(str,ls)))
    
def main():
    trash = input()
    ls = list(map(int, input().split(' ')))

    for i in range(1, len(ls)):
        printls(ls)
        v = ls[i]
        for j in reversed(range(0, i)):
            if ls[j] > v:
                ls[j], ls[j+1] = ls[j+1], ls[j]

    printls(ls)
    
if __name__ == '__main__':
    main()

Solution (Python):
def insertionSort(A,N):
    for i,v in enumerate(A):
        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 = [int(i) for i in 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):
_n = int(raw_input())
_a = [int(x) for x in raw_input().split()]

for i in range(1, _n):
    print(" ".join([str(x) for x 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(x) for x in _a]))

Solution (Python):
def insertion_sort(array):
    for i in range(len(array)):
        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

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

    return array

if __name__ == '__main__':
    element_number = int(input())
    input_array = list(map(int, input().split()))

    insertion_sort(input_array)

Solution (Python):
def insertion_sort(array):
    for i in range(len(array)):
        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

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

    return array

if __name__ == '__main__':
    element_number = int(input())
    input_array = list(map(int, input().split()))

    insertion_sort(input_array)

Solution (Python):

def print_A(A,N):
    stri = ""
    for i in range(N-1):
        stri+=str(A[i])+" "
    stri+=str(A[N-1])
    print(stri)

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

N=int(input())
A=[int(x) for x in input().split()]
print_A(A,N)
insertionSort(A,N)

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



if __name__ == "__main__":
    insert_sort()

Solution (Python):
import sys, re

def echo(A):
    for i, a in enumerate(A):
        if i < len(A) - 1:
            sys.stdout.write('%d ' % a)
        else:
            sys.stdout.write('%d\n' % a)

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


n = int(raw_input())
a_text = raw_input()
splits = re.split(' ', a_text)
a = []
for i, s in enumerate(splits): 
    if s:
        a.append(int(s))

insertionSort(a, n)

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

Solution (Python):
N = 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 insertionsort(x):
    x = list(map(int, x))
    for i in range(len(x)):
        for k in range(i, 0, -1):
            if x[k-1] > x[k]:
                x[k-1], x[k] = x[k], x[k-1]
        print(" ".join(map(str, x)))


if __name__ == "__main__":
    input()
    insertionsort(input().split(" "))

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

    insertion_sort(A, N)

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

    return A

if __name__ == '__main__':
    main()

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

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

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

Solution (Python):


def print_list(X):
    first_frag = True
    for val in X:
        if first_frag:
            print_line = str(val)
            first_frag = False
        else:
            print_line = print_line + ' ' + str(val)
    print(print_line)

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

print_list(A)

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

    print_list(A)

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

Solution (Python):

"""
Created on Sat Jun 17 09:19:58 2017

@author: syaga
"""


if __name__ == "__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)))

Solution (Python):

n = int(input())
num = list(map(int, input().split()))
for i in range(n):
    tmp = num[i]
    j = i 
    while j>0 and num[j-1] > tmp:
        num[j] = num[j-1]
        j -= 1
    num[j] = tmp
    for i in range(n):
        if i==n-1:
            print(num[i], end='')
            break
        print(num[i], end=' ')
    print()

Solution (Python):
N = int(input())
A = [int(A) for A in input().split()]
for k in range(N):
    if k == N -1:
        print("{}".format(A[k]))
    else:
        print("{}".format(A[k]), end = " ")
for i in range(1, N):
    j = i -1
    v = A[i]
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    for k in range(N):
        if k == N -1:
            print("{}".format(A[k]))
        else:
            print("{}".format(A[k]), end = " ")

Solution (Python):
n = int(input())
tmp = input()
print(tmp)
a = [int(x) for x in tmp.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):
def insertionSort(N,A): 
    for i in range(0,N):
        innum = A[i]
        j = i - 1
        while j>=0 and innum < A[j]:
            A[j+1] = A[j]
            j = j -1
        A[j+1] = innum
        for j in range(0,N):
            if j < N-1:
                print(A[j], end=" ")
            else:
                print(A[j])

    
    return A

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

Solution (Python):
N = int(input())
A = (input()).split()
for i in range(0,N):
    A[i] = int(A[i])
for i in range(0,N):
    innum = A[i]
    j = i - 1
    while j>=0 and innum < A[j]:
        A[j+1] = A[j]
        j = j -1
    A[j+1] = innum
    for j in range(0,N):
        if j < N-1:
            print(A[j], end=" ")
        else:
            print(A[j])

Solution (Python):
list_len = int(input().rstrip())
num_list = list(map(int, input().rstrip().split()))

for i in range(list_len):
    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
    
    output_str = ' '.join(map(str, num_list))
    print(output_str)

Solution (Python):
def printf(N, A):
    for cnt in range(N):
        if cnt == N - 1:
            print("{}".format(A[cnt]))
        else:
            print("{}".format(A[cnt]), end=' ')

N = int(input())
A = [int(A) for A in input().split()]
printf(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
    printf(N, A)

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

def main():
    N = int(input().rstrip())
    A = list(map(int, input().rstrip().split()))
    
    insertion_sort(A, N)
    
if __name__ == '__main__':
    main()

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


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

    print (*insertionSort(A, N))

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


def main():
    N = int(input().rstrip())
    A = list(map(int, input().rstrip().split()))
    
    insertion_sort(A, N)
    

if __name__ == '__main__':
    main()

Solution (Python):
def insertion(A):
    for i in range(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([str(x) for x in A]))

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

Solution (Python):
import sys

def printlist(lst):
	for l in lst:
		print(l),
	print

N = int(sys.stdin.readline().strip())
A = sys.stdin.readline().strip().split(" ")

A = map(lambda x:int(x),A)
for i in range(0,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
	printlist(A)

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

def print_list(A):
    for a in A[:-1]:
        print ("%d "%a, end="")
    print(A[-1])

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

InsertionSort(A, N)

Solution (Python):
import sys

def insert_sort(array):
    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
        print print_list(array)
    return array

def print_list(array):
    s = ""
    for n in array:
        s += str(n) + " "
    s = s.strip()
    return s
    
if __name__ == "__main__":
    array_num = int(sys.stdin.readline().strip())
    array = map(lambda x: int(x), list(sys.stdin.readline().strip().split(" ")))
    array = insert_sort(array)

Solution (Python):
s = int(input())
A = input().split()
for i in range(s):
    v = A[i]
    j = i - 1
    while j >=0 and int(A[j]) > int(v):
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = v
    print(" ".join(A))

Solution (Python):
def insertionSort(*args):
    l = list(args)
    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))

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

Solution (Python):


"""
?????\?????????

N ??????????´????????????°??? 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

????????????????????????????????¢?????´????????????????£??????????????????????
??¢?????´??????????????????????¢???????????????????????¨??????????????????§?????????
?????\?????´??????????????¨?????? i ??????????????????????????´?????????????????????????????????????????????

"""

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


num = int(input().strip())
arr = list(map(int,input().strip().split()))
iSort(arr,num)

Solution (Python):
def insertionSort(data):
	for old in range(len(data)):
		new = old
		while new>0 and data[old]<data[max(0,new-1)]:
			new -= 1
		i = data.pop(old)
		data.insert(new,i)
		yield data

input()
data = [int(s) for s in input().split()]
[print(' '.join([str(i) for i in d])) for d in insertionSort(data)]

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

    a = list(A)
    print(*a, sep=' ')
    insertionSort(a, N)

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, sep=' ')

main()

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

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

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=A.copy()
    B=list(map(str,B))
    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
    print(*A)

Solution (Python):
def insertionSort(a):
    for i,v in enumerate(a):
        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)

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

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

insertionSort(A, N)

Solution (Python):
n = raw_input()
A = map(int, raw_input().split())
for i in range(0, len(A)):
        if i == len(A)-1:
            print A[i]
        else:
            print A[i],
            
for i in range(1, len(A)):
    j = i - 1
    tmp = A[i]
    while A[j] > tmp and j >= 0:
        tmp2 = A[j]
        A[j] = tmp
        A[j+1] = tmp2
        j -= 1
        
    for i in range(0, len(A)):
        if i == len(A)-1:
            print A[i]
        else:
            print A[i],

Solution (Python):

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


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


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


N=int(input())
sl=input()
print(sl)
lis=list(map(int,sl.split()))
insertionSort(lis,N)

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

        j-=1
        z[j+1]=v
    print(' '.join(list(map(str, z))))

Solution (Python):


import sys, math, os


PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def printA(A):
    print(' '.join([str(a) for a in A]))

def insertion_sort(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
        printA(A)

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

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

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

Solution (Python):
def output(list):
    for i,row in enumerate(list):
        if i == 0:
            print(row,end='')
        else:
            print('',row,end='')
    
def main():
    s = input()
    s_list = []
    s_list = list(map(int,input().split()))

    output(s_list)
    print()

    i = 0
    for count in range(len(s_list)-1):


        if s_list[i] > s_list[i+1]:


            ins_num = s_list[i+1]
            s_list[i+1] = s_list[i]
            s_list[i]   = ins_num

            j = i - 1

            while j >= 0:
                if s_list[j] > ins_num:
                    s_list[j+1] = s_list[j]
                    s_list[j]   = ins_num

                j -= 1
            output(s_list)
        else:
           output(s_list)        
    
        print()
        i += 1

if __name__ == '__main__':
    main()

Solution (Python):
def sort(a):
    n = len(a)
    for i in range(1,n):
        for j in range(i):
            p = i-j
            if a[p] < a[p-1]:
                a[p], a[p-1] = a[p-1], a[p]
        print ' '.join(map(str, a))

n = int(raw_input())
a = map(int, raw_input().split(' '))
print ' '.join(map(str, a))
sort(a)

Solution (Python):
def print_1(array):
    for i in range(len(array)):
        if i == len(array) - 1:
            print(array[i])
        else:
            print(array[i], end=" ")

N = int(input())
A = [int(n) for n in input().split()]
print_1(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_1(A)

Solution (Python):
n = int(input())
a = map(int,raw_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 insertionSort(A, N):
    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

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

insertionSort(A, N)

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