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


if __name__ == "__main__":
	n = int(raw_input())
	array = map(int, raw_input().split())
	for i in range(1, n):
		print " ".join(map(str, 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 " ".join(map(str, array))

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

        array[j + 1] = v

        for i in range(amount - 1):
            print(array[i], end=" ")
        print(array[amount - 1])

amount = int(input())
array = [0 for i in range(amount)]
array = list(map(int, input().split()))

for i in range(amount - 1):
    print(array[i], end=" ")
print(array[amount - 1])

insertionSort(array, amount)

Solution (Python):


import time
import sys
import io
import re
import math
import itertools



mod=1000000007

pi=3.141592653589
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]

n=int(raw_input())
a=map(int,raw_input().split())
ans=chk=0
def prin(l):
    for i in l:
        print i,
    print

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

Solution (Python):

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

print(*numbers)

for i in range(1,n):
    tmp = numbers[i]
    j = i - 1

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

    print(*numbers)

Solution (Python):

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

for i in range(n):
    tmp = numbers[i]
    j = i - 1

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

    print(*numbers)

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

import sys

nums_len = int(sys.stdin.readline())
nums_str = sys.stdin.readline().split(' ')
nums = map(int, nums_str)

print ' '.join(map(str, nums))
for i in range(1, nums_len):
    for j in reversed(range(1, i + 1)):
        if nums[j] < nums[j - 1]:
            v = nums[j]
            nums[j] = nums[j - 1]
            nums[j - 1] = v
    print ' '.join(map(str, nums))

Solution (Python):

import sys

nums_len = int(sys.stdin.readline())
nums_str = sys.stdin.readline().split(' ')
nums = map(int, nums_str)

print ' '.join(map(str, nums))
for i in range(1, nums_len):
    v = nums[i]
    for j in reversed(range(0, i)):
        if v < nums[j]:
            nums[j + 1] = nums[j]
            nums[j] = v
        if v > nums[j]:
            break
    print ' '.join(map(str, nums))

Solution (Python):
def trace( nums ):
	output = []
	for num in nums:
		output.append( str( num ) )
		output.append( " " )
	output.pop( )
	print( "".join( output )  )

n = int( raw_input( ) )
nums = [ int( val ) for val in raw_input( ).split( " " ) ]
trace( nums )

for i in range( 1, len( nums ) ):
	key = nums[i]
	j = i - 1
	while 0 <= j and key < nums[j]:
		nums[ j+1 ] = nums[j]
		j -= 1
	nums[ j+1 ] = key
	trace( nums )

Solution (Python):
def trace( nums ):
	output = []
	for num in nums:
		output.append( str( num ) )
		output.append( " " )
	output.pop( )
	print( "".join( output )  )

n = int( input( ) )
nums = [ int( val ) for val in input( ).split( " " ) ]
trace( nums )

for i in range( 1, len( nums ) ):
	key = nums[i]
	j = i - 1
	while 0 <= j and key < nums[j]:
		nums[ j+1 ] = nums[j]
		j -= 1
	nums[ j+1 ] = key
	trace( nums )

Solution (Python):
n = int( raw_input( ) )
nums = [ int( val ) for val in raw_input( ).split( " " ) ]
print( " ".join( map( str, nums ) ) )

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

Solution (Python):
n = int( input( ) )
nums = [ int( val ) for val in input( ).split( " " ) ]
print( " ".join( map( str, nums ) ) )

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

Solution (Python):


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



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


n = int(raw_input().rstrip())
a = map(int, raw_input().rstrip().split())
insertionSort(a, n)

Solution (Python):


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


if __name__ == "__main__":
    N=int(input())
    arr=list(map(int,input().split()))
    print(*arr)
    InsertSort(N,arr)

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

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

Solution (Python):
N = int(raw_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):
def insertSort(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(i) for i in input().split()]
    print(' '.join(map(str, a)))
    insertSort(a, n)

Solution (Python):
def insertSort(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(i) for i in input().split()]
    print(' '.join(map(str, a)))
    insertSort(a, n)

Solution (Python):
N = int(raw_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):

import sys

def main():
	num = int(raw_input())
	list = map(int, raw_input().split())
	sort(num, list)

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


if __name__ == "__main__":
	main()

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

p = 1
print ' '.join(map(str, arr))
while True:
    if p >= len(arr):
        break
    for j in range(0,p):
        if arr[p] < arr[j]:
            arr[p],arr[j] = arr[j],arr[p]
    p += 1
    print ' '.join(map(str, arr))

Solution (Python):


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

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

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

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

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

n = int(raw_input())
a = map(int, raw_input().split(" "))
insertionSort(a, n)

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):
num = raw_input()
num_list = raw_input()
num_list = num_list.split()
print " ".join(num_list)

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

Solution (Python):
num = int(raw_input())
line = raw_input()

A = line.strip().split(" ")
print " ".join(A)


for i in range(1, num):
    v = int(A[i])
    j = i - 1
    for j in range(j, -1, -1):
        if int(A[j]) > v:
            A[j+1] = A[j]
            j -= 1
        else:
            break
    A[j+1] = str(v)
    
    print " ".join(A)

Solution (Python):
def insertionSort(a,n):
    for i in range(n):
        print(a[i],end="")
        if(i!=n-1):
            print(" ",end="")
    print("")    
    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):
            print(a[i],end="")
            if(i!=n-1):
                print(" ",end="")
        print("")

a=[]
n=int(input())
s=input()
a=list(map(int,s.split()))
insertionSort(a,n)

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

print " ".join(map(str,num_list))
for i in range(1, N):
    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
    print " ".join(map(str,num_list))

Solution (Python):
n = int(input())
A = []
s = input()
A = list(map(int,s.split()))
for i in range(1,len(A)):
    v = A[i]
    j = i-1

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

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

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

Solution (Python):
numbers = []
n = raw_input()
s = raw_input()
print s
numbers = s.split(" ")
for i in range(int(n)):
	numbers[i] = int(numbers[i])


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

Solution (Python):
import sys

def insertionSort(x_list,y):
  for i in range(1, y):
    v = x_list[i]
    j = i - 1
    while j >= 0 and x_list[j] > v:
      x_list[j + 1] = x_list[j]
      j -= 1
    x_list[j+1] = v
    for k in range(0, y):
      print x_list[k],
    print

y = sys.stdin.readline()
y = int(y)

x = sys.stdin.readline()

x_list = x.split(" ")

for i in range(y):
  x_list[i] = int(x_list[i])

for k in range(0, y):
  print x_list[k],
print

insertionSort(x_list, y)

Solution (Python):
import sys

lines = sys.stdin.readlines()

N = lines[0]
A = lines[1].strip().split(" ")

print " ".join(A)

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

Solution (Python):
N = int(raw_input())
A = raw_input().split(" ")

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

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

    A[j+1] = v

    print " ".join(A)

Solution (Python):

n = raw_input()
num = raw_input()
array = []
array = num.strip().split(" ")
int_array = map(int, array)

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

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

numbers = input()
numbers = numbers.split(' ')

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

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

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

print(*xs)
insertion_sort(xs)

Solution (Python):
N = input()
A = map(int, raw_input().split())
for i in range(len(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))

Solution (Python):
import copy

def insertion_sort(List):
	l=len(List)
	for i in range(l):
		for j in range(i):
			if List[i]<List[j]:
				temp=copy.copy(List)
				for k in range(j,i):
					List[k+1]=temp[k]
				List[j]=temp[i]
				break
		print(" ".join(map(str,List)))

N=input()
N_List=map(int,raw_input().split())
insertion_sort(N_List)

Solution (Python):




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


def insertion_sort(a, n):
    print_array(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_array(a)
    return a


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

if __name__ == "__main__":
    main()

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

for i in range(n):
    a = l[i]
    j = i - 1

    while j >= 0 and l[j] > a:
        l[j+1] = l[j]
        j = j - 1

    l[j+1] = a
    print(*l)

Solution (Python):
import sys

def insertionSort(A, N):
    for n in range(N-1):
        print (A[n], 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 = j - 1
        A[j + 1] = v
        
        for n in range(N-1):
            print (A[n], end=" ")
        print(A[N-1])
    return A

N = int(input())
A = input()
A = A.split(" ")
for i in range(N):
    A[i] = int(A[i])
val = insertionSort(A, N)

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

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

def display(inp):
    s = len(inp)
    for i in range(s):
        if i!=len(inp)-1:
            print("%d" % inp[i], end=" ")
        else:
            print("%d" % inp[i], end="")
    print("")

line = sys.stdin.readline()
size = int(line)
line = sys.stdin.readline()
inp = []
for i in line.split(" "):
    inp.append(int(i))

display(inp)

for i in range(1,size):
    if inp[i]!=size:
        check = inp.pop(i)
        for j in range(i):
            if check<inp[j]:
                inp.insert(j,check)
                break
            if j==i-1:
                inp.insert(j+1,check)
                break
    display(inp)

Solution (Python):
n = int(input())
array = [int(a) for a in input().split()]
for i in range(n):
    j = i
    while j < n:
        if j != 0 and array[j-1] > array[j]:
            array[j-1], array[j] = array[j], array[j-1]
            j -= 1
            continue
        else:
            break
    for k in range(n):
        if k != n-1:
            print(array[k], end=' ')
        else:
            print(array[k])

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

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

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

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

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

Solution (Python):
def 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 = 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 main():
    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) & (a[j] > v):
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        print ' '.join(map(str,a))
    return 0

main()

Solution (Python):
input()
array = [int(x) for x in input().split()]
print(' '.join(list(str(x) for x in 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(' '.join(list(str(x) for x in array)))

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

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

Solution (Python):
def insertionSort(R, n):
    for i in range(1, n):
        Now = R[i]
        j = i - 1
        while j >= 0 and R[j] > Now:
            R[j + 1] = R[j]
            j = j - 1
        R[j + 1] = Now
        trace(R, n)

def trace(R, n):
    for i in range(n):
        print R[i],
    print

n = input()
R = map(int, raw_input().split())

trace(R, n)
insertionSort(R, n)

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

def insertion_sort(raw_list):
    for i, v in enumerate(raw_list):
        if i == 0:
            continue
        j = i - 1
        while j >= 0 and v < raw_list[j]:
            raw_list[j+1] = v 
            raw_list[j+1] = raw_list[j]
            j -= 1
        raw_list[j+1] = v 
        print(' '.join([str(i) for i in raw_list]))

    return raw_list

print(' '.join([str(i) for i in data]))
insertion_sort(data)

Solution (Python):
def trace() :
    li=[]
    for i in xrange(n):
        li.append(str(a[i]))
    print(" ".join(li))
    
n=input()
a=map(int,raw_input().split())

for i in xrange(n):
    v=a[i]
    j=i-1
    while j>=0 and a[j]>v:
        a[j+1]=a[j]
        j-=1
    a[j+1]=v
    trace()

Solution (Python):
n = int(raw_input())
A = map(int,raw_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):
def insertionSort(a, n):
    for i in range(1, n):
        show(a, 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
    else:
        show(a, n)

def show(a, n):
    for i in range(n):
        if i == n-1:
            print "%d" % a[i]
        else:
            print "%d" % a[i],

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

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

Solution (Python):
def printlist(al):
    print " ".join(map(str,al))
        

l = input()
al = map(int,raw_input().split())
printlist(al)
for i in xrange(1,l):
    v = al[i]
    j = i-1
    while j >= 0 and al[j]>v:
        al[j+1] = al[j]
        j-=1
    al[j+1]=v
    printlist(al)

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

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

Solution (Python):
N = input()
l = map(int, raw_input().split())
i = 1
while i < N:
    l_str = map(str,l)
    print " ".join(l_str)
    tmp = l[i]
    j = i - 1
    while j >= 0 and tmp < l[j]:
        l[j + 1] = l[j]
        j -= 1
    l[j + 1] = tmp
    i += 1
l_str = map(str,l)
print " ".join(l_str)

Solution (Python):


N = int(raw_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):
n = int(input())
A = 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):
from __future__ import division, print_function, unicode_literals
from future_builtins import *

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

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

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

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

def printList(A, N):
    for i in xrange(N):
        print A[i],
    print


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

A = insertionSort(A, N)
printList(A, N)

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

for i in range(0, data_num):
    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(' '.join([str(n) for n in data]))

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

def sort_print(n, input_list):
    
    
    for i in range(n):
        index = i

        num = input_list[index]
        while index-1 >=0 and input_list[index-1] > num:
            input_list[index] = input_list[index-1]
            index -= 1
        input_list[index] = num

        result = [str(x) for x in input_list]
        print(' '.join(result))

sort_print(n, input_list)

Solution (Python):
def insert(array, index):
    value = array[index]
    for i in range(index - 1, -1, -1):
        if array[i] < value:
            array[i+1] = value
            break
        array[i + 1] = array[i]
    else:
        array[0] = value

def insertion_sort(array, log=False):
    for i in range(len(array)):
        insert(array, i)
        if log:
            print(*array)

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

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

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

Solution (Python):


import sys

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

for i in xrange(n):
  print a[i],
print
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
 for k in xrange(n):
  print a[k],
 print

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

if __name__=='__main__':
   n=int(input()) 
   A=list(map(int,input().split()))
   insertion_sort(A)
   print(*A)

Solution (Python):
import sys
import math

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

for i in xrange(n) :
    tmp = a[i]
    a.pop(i)

    for j in xrange(i) :
        if a[j] > tmp :
            a.insert(j, tmp)
            break
    else :
        a.insert(i, tmp)

    for j in xrange(n) :
        sys.stdout.write(str(a[j]))
        if j < n-1 :
            sys.stdout.write(" ")

    print

Solution (Python):
import string
n = int(input())
l = []
l = list(map(int, input().split()))
for i in range(n):
    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)))

Solution (Python):


num = int(input())

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

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

Solution (Python):
n = int(input())
arr = []
s = input().split()
for i in range(n):
    arr.append(int(s[i]))
for i in range(n):
    k = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > k:
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = k
    for i in range(n):
        if i == n-1:
            print(arr[i])
        else:
            print(arr[i], end=" ")

Solution (Python):
N = input()
A = map(int, raw_input().split())
for i in range(len(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))

Solution (Python):
n = int(input())
data = list(map(int, 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(" ".join(map(str, data)))

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

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

Solution (Python):
def ins(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
		for k in range(len(A)):
			if k==len(A)-1:
				print(A[k])
			else:
				print(A[k],end=" ")
N=int(input())
A=list(map(int,input().split(" ")))
ins(A,N)

Solution (Python):



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


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

Solution (Python):


import sys


def main():
  length = int(input())
  elements = list(map(int, input().split()))
  print(" ".join(str(i) for i in elements))

  sorted_list = [elements[0]]
  for i in range(1, length):
    element = elements[i]
    for j in range(0, len(sorted_list) + 1):
      if j == len(sorted_list):
        sorted_list.append(element)
      elif element < sorted_list[j]:
        sorted_list.insert(j, element)
        break
    output_list = sorted_list[0:i+1] + elements[i+1:]
    print(" ".join([str(i) for i in output_list]))

  return 0

if __name__ == '__main__':
  main()

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



print(" ".join(A))

for i in range(1, n):
    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):
n = int(input())
A = input().split(' ')



print(" ".join(A))

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

    while j >= 0 and int(A[j]) > int(v):
        A[j+1] = A[j]
        A[j] = v
        j -= 1
    print(" ".join(A))