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

Solution (Python):

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

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

Solution (Python):

def pprint(numlist):
  print(" ".join(map(str,numlist)))
N = int(input())
A = list(map(int, input().split()))
pprint(A)
for i in range(1,N):
  j = i
  v = A[i]
  while A[j] < A[j-1] and j >= 1:
    A[j] = A[j-1]
    A[j-1] = v
    j -= 1
  pprint(A)

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

Solution (Python):
num = int(input())
data = list(map(int, input().split()))
for i in range(num):
    for j in range(i, 0, -1):
        if data[j] < data[j-1]:
            data[j-1], data[j] = data[j], data[j-1]
    print(' '.join(map(str, data)))

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([str(x) for x in A]))

if __name__ == '__main__':
    length = int(input())
    hoge = [int(x) for x in input().split()]
    print (' '.join([str(x) for x in hoge]))
    insertionSort(hoge, length)

Solution (Python):
def insertionsort(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,sep=" ")
    return A

N = int(input())
A = [int(i) for i in input().split()]
print(*A,sep=" ")
insertionsort(A)

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

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

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

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

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

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

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

Solution (Python):



import sys

def prt_list(A):
    s_list = list(map(str, A))
    print(' '.join(s_list))


def insert_sort(A):
    prt_list(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
        prt_list(A)
    return

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

insert_sort(a)

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

length = int(input())
array = [int(x) for x in input().split()]

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

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

if __name__ == '__main__':
    n = int(input())
    array = list(map(int, input().split()))[0:n]
    insertion_sort(array)

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

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


def main():
    n = int(input())
    a = [int(i) for i in input().split(' ')]
    print(' '.join(str(i) for i in a))
    insertion_sort(a, n)


main()

Solution (Python):
import sys

input_len = int(input())
l = input().split()
sort_line = [0 for i in range(input_len)]
for i in range(input_len):
	sort_line[i] = int(l[i])
	

for k in range(input_len):
	if (k > 0):
		sys.stdout.write(" ")
	sys.stdout.write(str(sort_line[k]))
print()

for i in range(1, input_len):
	v = sort_line[i]
	j = i - 1
	while (j >= 0 and v < sort_line[j]):
		sort_line[j+1] = sort_line[j]
		j -= 1
	sort_line[j + 1] = v

	for k in range(input_len):
		if (k > 0):
			sys.stdout.write(" ")
		sys.stdout.write(str(sort_line[k]))
	print()

Solution (Python):
def InsertionSort(A, N):
    ans = ' '.join(map(str, A)) + '\n'
    i = 1
    while i < 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, A)) + '\n'
        i += 1
    return ans[:-1]

n = int(input())
A = list(map(int, input().split(' ')))
ans = InsertionSort(A, n)
print(ans)

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

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

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

N = eval(input())
A = list(map(int, input().split()))
showlist(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
    showlist(A)

Solution (Python):
n = input()
nums = input()
nums = nums.split()
nums = list(map(int, nums))
print(' '.join(map(str, nums)))

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

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

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

	print(*a)

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

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

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

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

N = int(input())
A = input()
Insertion_Sort(A, N)

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

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

y = list(map(str, array))
y = " ".join(y)
print(y)

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

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

n = input()
A = [int(x) for x in input().split()]
print(*insertion_sort(A))

Solution (Python):
def insertion_sort(alist):
    """sort alist by insertion sort.
    print the intermediate sequence for each step.

    >>> insertion_sort([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
    [1, 2, 3, 4, 5, 6]
    """
    for i, key in enumerate(alist):
        for j in reversed(range(i)):
            if alist[j] <= key:
                alist[j+1] = key
                break
            else:
                alist[j+1] = alist[j]
        else:
            alist[0] = key
        print(" ".join([str(i) for i in alist]))

    return alist


def run():
    _ = int(input())  
    nums = [int(i) for i in input().split()]

    insertion_sort(nums)


if __name__ == '__main__':
    run()

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

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

Solution (Python):
num = int(input())
cards = [int(i) for i in input().split()]

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

def output(cards):
	sorting = [str(i) for i in cards]
	print(" ".join(sorting))

insertion_sort(num, cards)

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

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

insertion_sort(A)

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

for x in range(1, len(s)):
    print(*s, sep=' ')
    stash = s[x]
    if stash < s[x-1]:
        y = x
        while True:
            s[y] = s[y-1]
            y -= 1
            if y == 0 or stash > s[y-1]:
                break
        s[y] = stash
print(*s, sep=' ')

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

"""
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
"""
mm = ''
for i in range(n):
    mm = mm + ' ' + str(l[i])
print(mm.strip())

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

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

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

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

insertion_sort(A_idx,n)

Solution (Python):
def insertionSort(a,n):
    for i in range(1,n):
        for k in range(n):
            print(a[k],end='')
            if k==n-1:
                print()
            else:
                print(' ',end='')

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

n=int(input())
r=input()
data=r.split(' ')
for i in range(n):
    data[i]=int(data[i])
insertionSort(data,n)

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

n = int(input())
a = input().split()
a = [int(i) for i in a]
pr(a)
insertionsort(a,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
        prt(A)

def prt(A):
    for i in A:
        if i != A[len(A)-1]: print(i, end=" ")
        else: print(i)

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

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

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
        pr(A,n)

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

Solution (Python):
N=int(input())
line=input().split()
A=[0]*N
for i in range(0,N):
    A[i]=int(line[i])
for i in range(N):
    """
    for k in range(N):
        print(A[k],end="")
        if k==N-1:
            print()
        else:
            print(" ",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 range(N):
        print(A[k],end="")
        if k==N-1:
            print()
        else:
            print(" ",end="")

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

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

insertion_sort(A_idx,n)

"""実行結果

6
4 6 3 2 1 5
4 6 3 2 1 5
4 6 3 2 1 5
3 4 6 2 1 5
2 3 4 6 1 5
1 2 3 4 6 5
1 2 3 4 5 6

"""

Solution (Python):
N=int(input())
A=[0 for i in range(N)]
A=input().split()
for i in range(N):
    A[i]=(int)(A[i])
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=" ")
        if k==N-1:
            print(A[k])

Solution (Python):
N=int(input())
A=[0 for i in range(N)]
A=input().split()
for i in range(N):
    A[i]=(int)(A[i])
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=" ")
        if k==N-1:
            print(A[k])

Solution (Python):
N=int(input())
A=[0 for i in range(N)]
A=input().split()
for i in range(N):
    A[i]=(int)(A[i])
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=" ")
        if k==N-1:
            print(A[k])

Solution (Python):


def Insertion_Sort():
    N=int(input())
    A=list(map(int,input().split()))
    for i in range(0,N):
        v=A[i]
        j=i-1
        while j>=0 and A[j]>v:
            A[j+1]=A[j]
            j=j-1
        A[j+1]=v
        
        print(A[0],end="")
        for i in range(1,N):
            print(" {}".format(A[i]),end="")
        print('\n',end="")
        


if __name__ == "__main__":
    Insertion_Sort()

Solution (Python):

def insertionsort(n,A):
	for i in range(n):
		t=A[i]
		j=i-1
		while j>=0 and A[j] > t:
			A[j+1]=A[j]
			j-=1
			A[j+1]=t
			
			
	
		for k in range(n):
			if k<n-1:
				print(A[k],end=" ")
			else:
				print(A[k])
			
n=int(input())
A=list(map(int, input().split()))

insertionsort(n,A)

Solution (Python):


def Insertion_Sort(N,A,flag=0):
    for i in range(0,N):
        v=A[i]
        j=i-1
        while j>=0 and A[j]>v:
            A[j+1]=A[j]
            j=j-1
        A[j+1]=v
        if flag==1:
            print(A[0],end="")
            for i in range(1,N):
                print(" {}".format(A[i]),end="")
            print('\n',end="")
    return A    


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


"""
(py361) [16D8101012J@ise72c ~]$ python ALDS1_1_A.py
10
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1
9 10 8 7 6 5 4 3 2 1
8 9 10 7 6 5 4 3 2 1
7 8 9 10 6 5 4 3 2 1
6 7 8 9 10 5 4 3 2 1
5 6 7 8 9 10 4 3 2 1
4 5 6 7 8 9 10 3 2 1
3 4 5 6 7 8 9 10 2 1
2 3 4 5 6 7 8 9 10 1
1 2 3 4 5 6 7 8 9 10
"""

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



for i in range(len(l)):
    v=l[i]
    j=i-1

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

    print(*l)

Solution (Python):

A = []



NUM =int(input())
A = input().split()

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

NUMLIST = range (1, NUM)


for i in NUMLIST:

  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(map(str, 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 = j-1
        A[j+1] = v
        for i in range(n-1):
            print(A[i],"",end="")
        print(A[n-1])

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

insertion_sort(A_idx,n)

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

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

Solution (Python):
import copy


def parse_stdin(input_lines: int):
    data_list = []
    for i in range(input_lines):
        data_list.append(input().rstrip().split())
    return data_list


def insertion_sort_with_print(values):
    print_now_state(values)
    for i, value in enumerate(values[1:]):
        i += 1
        j = i - 1
        while j >= 0 and values[j] > value:
            values[j + 1] = copy.copy(values[j])
            j -= 1
        values[j + 1] = copy.copy(value)
        print_now_state(values)


def print_now_state(values):
    for val_print in values[:-1]:
        print("{}".format(val_print), end=' ')
    print("{}".format(values[-1]), end='')
    print()


def main():
    input()
    input_lists = parse_stdin(1)
    values = list(map(int, input_lists[0]))
    insertion_sort_with_print(values)


if __name__ == '__main__':
    main()

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

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

for i in range(x):
    v = li[i]
    j = i - 1
    while j >= 0 and li[j] > v:
        li[j+1] = li[j]
        j -= 1
    li[j+1] = v
    for j in range(x):
        if j != x-1:
            print(li[j], end=" ")
        elif j == x-1:
            print(li[j], end="\n")

Solution (Python):
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())
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())
A=[0 for i in range(n)]

A=input().split()

for i in range(n):
    A[i]=(int)(A[i])

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

    for i in range(n):
        if i!=n-1:
            print(A[i],end=" ")
        if i==n-1:
            print(A[i])

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 0 <= j and v < a[j]:
    a[j+1] = a[j]
    j -= 1
  a[j+1] = v
  print(*a)

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

list=list(map(int,input().split()))
for i2 in range(len(list)):
    if i2!=len(list)-1:
        print(list[i2],end=' ')
    else :
        print(list[i2])

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

Solution (Python):



N = int(input())
nums = [int(x) for x in input().split(' ')]

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

Solution (Python):
def print_array(a):
    s = str(a[0])
    for i in range(1,n):
        s += ' '+str(a[i])
    print(s)
    return 0
n = int(input())
a = list(map(int, input().split()))

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)

Solution (Python):
def print_tmp(a_li):
    s = [str(a) for a in a_li]
    t = ' '.join(s)
    print(t)


n = int(input())
a = input()
A = [int(i) for i in a.split(' ')]
print_tmp(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_tmp(A)

Solution (Python):
N=int(input())
A=[0 for i in range(N)]
A=input().split()
for i in range(N):
    A[i]=(int)(A[i])
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 i in range(N):
        if i!=N-1:
            print(A[i],end=" ")
        if i==N-1:
            print(A[i])

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

Solution (Python):
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())
A = [int(x) for x in 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())
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):
_ = int(input())
a = list(map(int, input().split()))

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

Solution (Python):

def InsertionSort(l):
    print(" ".join(map(str, l)))
    
    for idx in range(1, len(l)):
        jdx = idx - 1
        while jdx >= 0 and l[idx] < l[jdx]:
            l[jdx], l[idx] = l[idx], l[jdx]
            idx -= 1
            jdx -= 1

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

def main():
    _ = input()
    in_list = list(map(int, input().split(' ')))
    
    InsertionSort(in_list)


main()

Solution (Python):



def show(A):
    for k in range(N):
        if k == N - 1:
            print('{0}'.format(A[k]))
        else:
            print('{0}'.format(A[k]), end=' ')


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

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

    show(A)

Solution (Python):
import sys

n = int(input())

line_number = [int(i) for i in sys.stdin.readline().split()]

print(' '.join([str(s) for s in line_number]))

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

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

def insertion_sort(array, n):
    print_out(array)
    for i in range(1,n):
        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_out(array)

def print_out(array):
    array_str = [str(i) for i in array]
    print(" ".join(array_str))

insertion_sort(ary, N)

Solution (Python):
"""
挿入ソート
"""
def insertion_sort(args):
    results = []
    for i in range(0, len(args)):
        v = args[i]
        j = i - 1
        while (j >= 0 and args[j] > v):
            args[j+1] = args[j]
            j -= 1
        args[j+1] = v
        results.append(args[:])
    return results

if __name__ == '__main__':
    n = int(input())
    args = list(map(int, input().split()))[0:n]
    results = insertion_sort(args)
    for result in results:
        print(' '.join(map(str, result)))

Solution (Python):
def insertion_sort(l):
    print(' '.join(map(str, l)))
    for i in range(1, len(l)):
        tmp = l[i]
        for j in range(i-1, -1, -1):
            if l[j] > tmp:
                l[j+1] = l[j]
            else:
                l[j+1] = tmp
                break
        else:
            l[0] = tmp
        print(' '.join(map(str, l)))
    return l

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

    insertion_sort(l)

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



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

    print(' '.join(map(str, l)))
    insertion_sort(l)

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


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


def insertion_sort(ary, verbose=True):

    for i in range(1, N):

        if verbose:
            print(' '.join([str(_) for _ in ary]))

        v = ary[i]
        j = i - 1

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

        ary[j + 1] = v

    print(' '.join([str(_) for _ in ary]))


insertion_sort(ary)