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

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

for i in range( nums ):
    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(*array)

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

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

insertion_sort(data, 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
    print(" ".join(list(map(str, A))))

Solution (Python):
n = int(input())
lst = map(int,raw_input().split())
for i in range(len(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 ' '.join(map(str, lst))

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

array = input().split()

intarr = [int(x) for x in array]
for x in intarr:
    if x == intarr[-1]:
        print(x)
    else:
        print(x,end=' ')


for c in range(1,n):
    v = intarr[c]
    j = c-1
    while j>=0 and intarr[j]>v:
        intarr[j+1] = intarr[j]
        j -= 1
    intarr[j+1] = v
    for x in intarr:
        if x == intarr[-1]:
            print(x)
        else:
            print(x, end=' ')

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

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

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

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

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

insertionsort(data, n)

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

print(*A)

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

Solution (Python):
def inserts(N):
    k = 1
    for n in N:
        print(n, end='')
        if k < len(N):
            print(' ', end='')
        k += 1

    print('')
    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
        k = 1
        for n in N:
            print(n, end='')
            if k < len(N):
                print(' ', end='')
            k += 1
        print('')


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

inserts(numbers)

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

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

Solution (Python):
def inputInline():
    N = int(input())
    numbers = list(map(int, input().split(" ")))
    return numbers


def insertionSort(numbers):
    N = len(numbers)
    for i in range(1, N):
        print(" ".join(list(map(str, numbers))))
        j = i - 1
        temp = numbers[i]
        while True:
            if j == -1:
                numbers[0] = temp
                break
            if temp < numbers[j]:
                numbers[j + 1] = numbers[j]
                j -= 1
            else:
                numbers[j + 1] = temp
                break
    return " ".join(list(map(str, numbers)))


print(insertionSort(inputInline()))

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

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

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

Solution (Python):


input()
seq = [int(x) for x in input().split()]
for i in range(0, len(seq)):
    key = seq[i]
    j = i - 1
    assert isinstance(i, int)
    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):
n = int(input())

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

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

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

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

    return A

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

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

Solution (Python):
a = []
def outputList(a):
	for i in range(len(a)):
		if i != len(a)-1:
			print("%d"%a[i],end=' ')
		else:
			print("%d"%a[i],end='\n')

n = int(input().strip())
for i in input().split():
	a.append(int(i))
	if len(a)==n:
		break
for i in range(1,len(a)):
	outputList(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
outputList(a)

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


if __name__ == "__main__":
    n = int(input())
    lst = [int(n) for n in input().split()]
    print(" ".join([str(n) for n in lst]))
    insertionSort(lst, n)

Solution (Python):
def insertionSort(lst, n):
    print(" ".join([str(n) for n in lst]))
    for i in range(1, n):
        v = lst[i]
        for j in range(0, i):
            if lst[j] > v:
                lst.insert(j, lst.pop(i))
                break

        print(" ".join([str(n) for n in lst]))

    return lst


if __name__ == "__main__":
    n = int(input())
    lst = [int(n) for n in input().split()]
    insertionSort(lst, n)

Solution (Python):
def insersionSort(A, N):
    for i in range(1, N):
        print " ".join([str(k) for k 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
    return A

if __name__ == "__main__":
    N = int(raw_input())
    A = map(int, raw_input().split())
    A = insersionSort(A, N)
    print " ".join([str(k) for k in 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):
kazu=int(input())
A=[int(i) for i in input().split()]



j=0
for i in range(kazu - 1):
    print(A[i], end=" ")
print(A[kazu-1])

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

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

Solution (Python):
def insertion_sort(A, N):
    for i in range(1, N):
        v = A[i]
        j = i - 1
        print(*A)

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

    return A

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

A = insertion_sort(A, N)
print(*A)

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

def print_list(list):
	for i in range(len(list)-1):
		print(list[i]),
	print(list[len(list)-1])


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)

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()))
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):
import sys
readline = sys.stdin.readline
def insertionSort(n, 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(readline())
A = [int(j) for j in readline().split(" ")]
insertionSort(n, A)

Solution (Python):
def main():

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

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


main()

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

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

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

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

def intersection(A,N):

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

intersection(A,num)

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

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

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

    print(" ".join(map(str, lst)));

    for i in range(1,n) :
        for j in reversed(range(i+1)) :
            if j == 0 :
                break
            elif lst[j] < lst[j-1]:
                lst[j], lst[j-1] = lst[j-1], lst[j]
        print(" ".join(map(str, lst)))






if __name__ == '__main__' :
    main()

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):
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())
numbs = list(map(int,input().split()))
print(' '.join(map(str,numbs)))
for i in range(1,len(numbs)):
    key = numbs[i]
    j = i-1
    while j >=0 and numbs[j] > key:
        numbs[j+1] = numbs[j]
        j -= 1
    numbs[j+1] = key
    print(' '.join(map(str,numbs)))

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


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

insertionSort(a,n)

Solution (Python):


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

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
			
if __name__ == '__main__':
	main()

Solution (Python):
NN=raw_input()
N=raw_input()
N = [int(i) for i in N.split()]
print ' '.join([str(k) for k in N])

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

Solution (Python):
def show_list(target):
    for i, item in enumerate(target):
        if i == len(target) - 1:
            print(item)
        else:
            print(item, end=" ")

def insection_sort(target):
    for i in range(1, len(target)):
        show_list(target)
        j = i - 1
        while j >= 0:
            if target[j] > target[j+1]:
                target[j], target[j+1] = target[j+1], target[j]
                j -= 1
            else:
                break
    return target

if __name__ == "__main__":
    n = input()
    a = [int(x) for x in input().split()]
    answer = insection_sort(a)
    show_list(answer)

Solution (Python):
n = int(input())
line = input()
arr = line.split(" ")
nums = []
for c in range(n):
    nums.append(int(arr[c]))

def trace(n_list):
    n_list_str = ""
    for num in n_list:
        n_list_str += str(num)
        n_list_str += " "
    print(n_list_str.rstrip(" "))
            
print(line)
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
    trace(nums)

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

Solution (Python):
import sys

ERROR_INPUT = 'input is invalid'


def main():
    n = get_length()
    arr = get_array(length=n)
    print(*arr)

    insetionSort(li=arr, length=n)
    return 0


def get_length():
    n = int(input())
    if n < 0 or n > 100:
        print(ERROR_INPUT)
        sys.exit(1)
    else:
        return n


def get_array(length):
    nums = input().split(' ')
    return [str2int(string=n) for n in nums]


def str2int(string):
    n = int(string)
    if n < 0 or n > 1000:
        print(ERROR_INPUT)
        sys.exit(1)
    else:
        return n


def insetionSort(li, length):
    for i in range(1, length):
        v = li[i]
        j = i - 1
        while j >= 0 and li[j] > v:
            li[j + 1] = li[j]
            j -= 1

        li[j + 1] = v
        print(*li)


main()

Solution (Python):
import sys

ERROR_INPUT = 'input is invalid'


def main():
    n = get_length()
    arr = get_array(length=n)

    insetionSort(li=arr, length=n)
    return 0


def get_length():
    n = int(input())
    if n < 0 or n > 100:
        print(ERROR_INPUT)
        sys.exit(1)
    else:
        return n


def get_array(length):
    nums = input().split(' ')
    return [str2int(string=n) for n in nums]


def str2int(string):
    n = int(string)
    if n < 0 or n > 1000:
        print(ERROR_INPUT)
        sys.exit(1)
    else:
        return n


def insetionSort(li, length):
    for n in range(0, length):
        print(*(sorted(li[0:n + 1]) + li[n + 1:length]))


main()

Solution (Python):


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

N = input()
A = map(int, raw_input().split())
for i in A:
    print i,
else:
    print
insertionSort(A,N)

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

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

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

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)))
        
insertionSort(a,n)

Solution (Python):


import sys

class Algo:
  @staticmethod
  def insersion_sort(A, N):
    for i in range(1, N):
      for k in A:
        if k==A[len(A)-1]:
          print(k)
        else:
          print(k, " ", sep="", end="")
      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 A:
      if k==A[len(A)-1]:
        print(k)
      else:
        print(k, " ", sep="", end="")

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

Solution (Python):


import sys

class Algo:
  @staticmethod
  def insersion_sort(A, N):
    for i in range(1, N):
      for k in A:
        if k==A[len(A)-1]:
          print(k)
        else:
          print(k, " ", sep="", end="")
      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 A:
      if k==A[len(A)-1]:
        print(k)
      else:
        print(k, " ", sep="", end="")

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

Solution (Python):
import sys
def print_list(A):
    for k in range(len(A)):
        sys.stdout.write(str(A[k]))
        if not k == len(A) -1: sys.stdout.write(" ")
    print()
def insert_sort(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 = j-1
        A[j+1]=v
        print_list(A)


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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
def insertion_sort(A, N):
    for i in range(1, N):
        for s in A:
            tmp = str(s) if A[0] == s else " "+str(s)
            print(tmp, end="")
        print()

        j = i-1
        v = A[i]
        while v < A[j] and j >= 0:
            A[j+1] = A[j]
            j = j-1
        A[j+1] = v
    for s in A: 
        tmp = str(s) if A[0] == s else " "+str(s) 
        print(tmp, end="")
    print()
    
if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split()]

    insertion_sort(A, N)

Solution (Python):
def insersion_sort(a):
    print(*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()
insersion_sort([int(i) for i in input().split()])

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

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

Solution (Python):
N=int(input())
arr=list(map(int,input().split()))
print(' '.join(map(str,arr)))
for key in range(1,len(arr)):
    temp=arr[key]
    i=key-1
    while i>=0 and arr[i]>temp:
        arr[i+1]=arr[i]
        i-=1
    arr[i+1]=temp
    print(*arr)

Solution (Python):
import sys

a = ""
l = []
for input in sys.stdin:
    a += input
l = a.split()
b = int(l[0])
l = l[1:]
for i in range(0,b):
    key = int(l[i])
    j = i - 1
    while(j >= 0 and int(l[j]) > key):
        l[j+1] = l[j]
        j = j - 1
    l[j+1] = key
    if(b > 0):
        for data in l:
            print int(data),
        print
    b = b-1

Solution (Python):
def listprint(lists):
	global N
	count = 0
	for i in lists:
		count += 1
		if count < N:
			print(i, end = ' ')
		if count == N:
			print(i)

if __name__ == '__main__':
	N = int(input())
	l = input().split()

	for i in range(N):
		l[i] = int(l[i])

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

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

res = v.copy()

for i in range(n):
    if i == 0:
        pass
    else:
        for j in range(i):
            if res[j] > v[i]:
                res.pop(i)
                res.insert(j, v[i])
                break

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

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

if __name__ == '__main__':

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

    A = insertionSort(A, N)
    print(" ".join(map(str, A)))

Solution (Python):
n=int(input())
s=input().split(' ')

print(' '.join(s))

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

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

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

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

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

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

pri(lst)
for i in range(1,n):
    v = lst[i]
    j = i-1
    while True:
        if j < 0:
            lst[0] = v
            break
        if lst[j] > v:
            lst[j+1] = lst[j]
            j -= 1
        else:
            lst[j+1] = v
            break
    pri(lst)

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

def insertationSort(nums,intNums):
    print(' '.join(nums))
    for i in range(1,len(nums)):
        v = intNums[i]
        j = i - 1
        while j>=0 and intNums[j]>v:
            intNums[j+1] = intNums[j]
            j = j - 1
        intNums[j+1] = v
        nums = list(map(str,intNums))
        print(' '.join(nums))

insertationSort(nums,intNums)

Solution (Python):
count = int(input());
data = [int(n) for n in input().split(" ")];

def insert_sort(data):
    show(data);
    for i in range(1, len(data)):
        n = data[i];
        j = i - 1;
        while j >= 0 and data[j] > n:
            data[j + 1] = data[j];
            j -= 1;
        data[j + 1] = n;
        show(data);

def show(data):
    print(" ".join(str(n) for n in data));

insert_sort(data);

Solution (Python):
def trace(A,input_num):
    for i in range(input_num):
        if i != input_num - 1:
            print(A[i],end = " ")
        else:
            print(A[i])

def insertionSort(A,input_num):
    for i in range(input_num):
        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,input_num)
        
input_num = int(input())
A = list(map(int, input().split()))

insertionSort(A,input_num)

Solution (Python):
def insertionSort(A,input_num):
    for i in range(input_num):
        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_num = int(input())
A = list(map(int, input().split()))

insertionSort(A,input_num)

Solution (Python):
def insertionSort(A,input_num):
    for i in range(input_num):
        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_num = int(input())
A = list(map(int, input().split()))

insertionSort(A,input_num)

Solution (Python):

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

n =  int(raw_input())
array = raw_input().split()
insertsort(array, n)

Solution (Python):
def insertSort(a):
    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([str(x) for x in a]))

if __name__ == '__main__':

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

    insertSort(a)