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



Sample input:
6
5 2 4 6 1 3


Sample output:
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

Submission status: Accepted

Solution code:
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([str(n) for n in A]))

Submission status: Accepted

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

for i in range(1, N):
    print(" ".join(map(str, A)))
    for j in range(i-1, -1, -1):
        if A[j] < A[j+1]:
            break
        A[j], A[j+1] = A[j+1], A[j]
print(" ".join(map(str, A)))

Submission status: Accepted

Solution code:
def InsertionSort(A, N):
    for i in range(N):
        v = A[i]       # A[i]は未ソート部分の先頭
        j = i - 1
        while j >= 0 and A[j] > v: 
            A[j+1] = A[j]  # vよりも大きい要素を一つ右に移動させる
            j -= 1     # 比較する位置を移動
        A[j+1] = v     # 空いた部分にvを入れる
        print(*A)

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

InsertionSort(A, N)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
list_cards = [0]*N
list_cards = 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        

        A_str = list(map(str, A))
        print(" ".join(A_str))

    return(A)

result_cards = insertionsort(list_cards, N)

Submission status: Accepted

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

n = int(input())
A = list(map(int, input().split()))
print(' '.join(map(str, A)))
insertion_sort(A)

Submission status: Accepted

Solution code:
# Indertion Sort

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

def insertSort(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)
	return 0

insertSort(A)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
print(*A)

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

Submission status: Accepted

Solution code:
N=int(input())
R=list(map(int,input().split()))

print(*R)

for n in range(1,N):
    if R[n-1]<=R[n]:
        pass
    elif R[n-1]>R[n]:
        v=R[n]
        for i in R[:n]:
            if i>v:
                j=R.index(i)
                break
        R[j+1:n+1]=R[j:n]
        R[j]=v
    print(*R)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def printData(data):
    for d in data:
        val = f'{d}'
        if data[-1] != d:
            end = " "
        else:
            end = "\n"
        print(f'{d}',end=end)

num = int(input())
data = list(map(int,input().split()))

printData(data)

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

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n=int(input())
#li1=list(map(int,input().split())) #li=[int(x) for x in input.split()] 
li=[int(x) for x in input().split()]

#print(li1,li2)
for i in range(n):
    v = li[i]
    j = i-1
    while j >= 0 and li[j] > v:
        li[j+1] = li[j]
        j-=1
    li[j+1] = v
    l=[str(a) for a in li]
    l=" ".join(l)
    print(l)

Submission status: Accepted

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

Submission status: Accepted

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

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


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

    trace()

Submission status: Accepted

Solution code:
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
    for k in range(n):
        if k != n-1:
            print(a[k], end=' ')
        else:
           print(a[k], end='') 
    print()

Submission status: Accepted

Solution code:
def insertSort(a,n):
    L=[str(ai) for ai in a]
    L=" ".join(L)
    print(L)
    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;
        L=[str(ai) for ai in a]
        L=" ".join(L)
        print(L)
        
n = int(input())
a = list(map(int,input().split()))
insertSort(a,n)

Submission status: Accepted

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

print(*A)
for i in range(1, n):
    t = A[i]
    k = i - 1
    while k >= 0 and t < A[k]:
        A[k + 1] = A[k]
        k -= 1
    A[k + 1] = t
    print(*A)

Submission status: Accepted

Solution code:
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
        for j in range(N-1) :
            print(A[j],  end=" ")
        print(A[N-1])
    


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

insertionSort(A, N)

Submission status: Accepted

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

print(' '.join([str(x) for x in a]))

for i in range(1, n):

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

    a[j+1] = v

    print(' '.join([str(x) for x in a]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

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


def p(N):
    for i in range(len(N)):
        if i == len(N) - 1:
            print(N[i])
        else:
            print(N[i], end=" ")


p(A)

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

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

    A[j + 1] = s

    p(A)

Submission status: Accepted

Solution code:
N=int(input())
lst=list(map(int,input().split()))
print(' '.join(map(str,lst)))

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

Submission status: Accepted

Solution code:
n = int(input())
A = [int(_) for _ 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)))

Submission status: Accepted

Solution code:
def print_list(l):
    print(' '.join(map(str, l)))


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

print_list(l)

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

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
    j=i-1
    insertion_A=A[i]
    while j >= 0:
        if A[j] > insertion_A: 
            A[j+1] = A[j] 
        else:
            break
        j -= 1
    A[j+1]=insertion_A
    print(*A)

Submission status: Accepted

Solution code:
n = int(input())
*lst, = map(int, input().split())

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
As = [int(x) for x in input().split()]

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

Submission status: Accepted

Solution code:
#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/aizu/alds11a_insertionSort.py
#


def insertionSort(a: list, n: int):
    a_string_list = map(str, a)
    output = ' '.join(a_string_list)
    print(output)
    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
        a_string_list = map(str, a)
        output = ' '.join(a_string_list)
        print(output)


n = int(input())
a = list(map(int, input().split()))
# print(a)
insertionSort(a, n)

Submission status: Accepted

Solution code:
# -*- coding:utf8 -*-

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

Submission status: Accepted

Solution code:
# 挿入ソート

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


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


insertionSort(A, N)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
print(' '.join(map(str, A)))
'''
for i in range(n):
    print(A[i], 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=' ')
    print('')
    '''
    print(' '.join(map(str, A)))

Submission status: Accepted

Solution code:
def insertionSort(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
        for i in range(len(A)):
            if i == len(A)-1:
                print(A[i],end="\n")
            else:
                print(A[i],end=" ")

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = input()
A = list(map(int, input().split()))
for index in range(len(A)):
    if index != len(A) - 1:
        print(A[index], end=" ")
    else:
        print(A[index])

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

Submission status: Accepted

Solution code:
def insertion_sort(lst):
    for i in range(1, 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(*lst)

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

Submission status: Accepted

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

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

		for item in range(len(A)):
			if item == len(A)-1:
				print(A[item])
			else:
				print(A[item],end=" ")

for item in range(len(L)):
	if item == len(L)-1:
		print(L[item])
	else:
		print(L[item],end=" ")

InsertionSort(L,n)






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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def insert_sort(A, N):
    print(*A, sep=' ')
    for i in range(1, N):
        tmp = A[i]
        j = i-1
        while j>=0 and A[j]>tmp:
            A[j+1] = A[j]
            j -= 1
            A[j+1] = tmp
        print(*A, sep=' ')

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

insert_sort(A, N)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a = [int(i) for i in 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
    for k in range(N):
        arra = ' '.join([str(n) for n in a])

    print(arra)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
# A = [int(i) for i in input().split()]
# for i in range(N):print(A[i],end='')
# print(end='\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 i in range(N):print(A[i],end=' \n'[i+1==N])
    # print(end='\n')

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
def printA():
    for i in range(0, N-1):
            print(A[i], '', end='')
    print(A[N-1])

for i in range(0,N):
    v = A[i]
    for j in range(i,-1,-1):
        if A[j-1] <= v or j == 0:
            A[j+1:i+1] = A[j:i]
            A[j] = v
            break
    printA()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
print(*A)

for i, a in enumerate(A):
    if i == 0:
        continue
    
    j = i-1
    while j >= 0 and A[j]>a:
        A[j], A[j+1] = a, A[j]
        j -= 1
    
    print(*A)

Submission status: Accepted

Solution code:
n=int(input())
table=list(map(int,input().split()))

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

insertsort(table,n)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
import sys

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

if len(A) != N:
  print("[ERROR] Number of Input integer is invalid")
  sys.exit()

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

def spaced_to_ints(spaced_some):
    return [int(a) for a in spaced_some.split(" ")]

def order_sequence_chars(str):
    return list(str)

def get_dice():
    input_data = input().split(" ")
    items = [int(cont) for cont in input_data]
    keys = ['T', 'S', 'E', 'W', 'N', 'B']
    return dict(zip(keys, items))

def rot_dice(rot, dice):
    if rot == "N":
        keys = ['T', 'S', 'B', 'N']
        items = dice['S'], dice['B'], dice['N'], dice['T']
        new_dice = dict(zip(keys, items))
        dice.update(new_dice)

    if rot == "S":
        keys = ['T', 'S', 'B', 'N']
        items = dice['N'], dice['T'], dice['S'], dice['B']
        new_dice = dict(zip(keys, items))
        dice.update(new_dice)

    if rot == "E":
        keys = ['T', 'E', 'B', 'W']
        items = dice['W'], dice['T'], dice['E'], dice['B']
        new_dice = dict(zip(keys, items))
        dice.update(new_dice)

    if rot == "W":
        keys = ['T', 'E', 'B', 'W']
        items = dice['E'], dice['B'], dice['W'], dice['T']
        new_dice = dict(zip(keys, items))
        dice.update(new_dice)

    if rot == "R":
        keys = ['N', 'W', 'S', 'E']
        items = dice['E'], dice['N'], dice['W'], dice['S']
        new_dice = dict(zip(keys, items))
        dice.update(new_dice)

    if rot == "L":
        keys = ['N', 'W', 'S', 'E']
        items = dice['W'], dice['S'], dice['E'], dice['N']
        new_dice = dict(zip(keys, items))
        dice.update(new_dice)

def search_right_surf(conds, dice):
    a, b = conds
    a_key = [k for k, v in dice.items() if v == a]
    b_key = [k for k, v in dice.items() if v == b]
    key_list = a_key + b_key

    part_st = ''.join(key_list)

    def search(part_st):
        if part_st in "TNBST":
            return "W"

        if part_st in "TSBNT":
            return "E"

        if part_st in "TEBWT":
            return "N"

        if part_st in "TWBET":
            return "S"

        if part_st in "NESWN":
            return "B"

        if part_st in "NWSEN":
            return "T"

    target_key = search(part_st)
    print(dice[target_key])

def search_top_surf(top_surf, dice):

    dice2_surf, *_ = [k for k, v in dice.items() if v == top_surf]

    if dice2_surf == 'N':
        rot_dice("S", dice)

    if dice2_surf == 'B':
        controls = list("SS")
        for i in controls:
            rot_dice(i, dice)
    if dice2_surf == 'S':
        controls = list("N")
        for i in controls:
            rot_dice(i, dice)
    if dice2_surf == 'W':
        controls = list("E")
        for i in controls:
            rot_dice(i, dice)
    if dice2_surf == 'E':
        controls = list("W")
        for i in controls:
            rot_dice(i, dice)

def search_flont_surf(flont_surf, dice):

    dice2_surf, *_ = [k for k, v in dice.items() if v == flont_surf]

    if dice2_surf == 'E':
        controls = list("R")
        for i in controls:
            rot_dice(i, dice)

    if dice2_surf == 'S':
        controls = list("RR")
        for i in controls:
            rot_dice(i, dice)

    if dice2_surf == 'W':
        rot_dice("L", dice)

def rot_compare(dice1, dice2):

    def compare_dice(dice1, dice2):
        if dice1 == dice2:
            return True

    comb = ["N", "S", "E", "W", "R", "L"]
    tups = list()
    for i in range(6):
        tups.append(itertools.combinations(comb, i))

    if compare_dice(dice1, dice2):
        return True

    for commands in itertools.chain.from_iterable(tups):
        for command in commands:
            rot_dice(command, dice2)
            if compare_dice(dice1, dice2):
                return True
    return False

def compare_many_dices(dice_list):
    dice1 = dice_list.pop(0)
    for dice2 in dice_list:
        if rot_compare(dice1, dice2):
            return True
    return False

def q1():

    dice = get_dice()
    controls = list(input())
    for i in controls:
        rot_dice(i, dice)
    print(dice["T"])

def q2():

    dice = get_dice()
    a = input()
    repeater = int(a)

    for neee in range(repeater):
        control_input = input().split(" ")
        conds = [int(i) for i in control_input]
        search_right_surf(conds, dice)

def q3():
    dice1 = get_dice()
    dice2 = get_dice()

    if rot_compare(dice1, dice2):
        print("Yes")
    else:
        print("No")

def q4():
    inp = input()
    dice_num = int(inp)
    dice_list = list()
    for i in range(dice_num):
        dice_list.append(get_dice())

    if compare_many_dices(dice_list):
        print("No")

    else:
        print("Yes")

def alds1():
    n = int(input())
    A = [int(cont) for cont in input().split(" ")]

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

    for _i in range(len(A)-1):
        i = _i+1
        v = A[i]
        j = i-1

        while j >= 0:
            if A[j] < v:
                break

            A[j+1] = A[j]
            A[j] = v
            j = j - 1

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

def itp2_1_a():
    def input_query(inp):
        que = spaced_to_ints(inp)
        return

alds1()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ALDS1_1_A: Insertion Sort
N = int(input())
A = list(map(int, input().split())) 

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    j = i-1
    key = a[i]
    #print(key)
    while 0 <= j and key < a[j]:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = key
    print(" ".join(map(str,a)))

Submission status: Accepted

Solution code:
N = int(raw_input())
A = list(map(int,raw_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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))

print(' '.join(map(str,L)))
for i in range(1,N):
    for j in range(i):
        if L[i] < L[j]:
            v=L.pop(i)
            L.insert(j,v)
            
    print(' '.join(map(str,L)))

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
from typing import MutableSequence


def insertion_sort(A_list: MutableSequence, num: int) -> None:
    """挿入ソート"""
    for i in range(num):

        j = i
        tmp = A_list[i]

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

        A_list[j] = tmp
        print_list = [str(i) for i in A_list]
        print(' '.join(print_list))


if __name__ == '__main__':
    n = int(input())
    input_list = [int(x) for x in input().split()]

    insertion_sort(input_list, n)

Submission status: Accepted

Solution code:
def print_list(num_list):
    print(" ".join(map(str, num_list)))

N = int(input())

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

print_list(A)

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

Submission status: Accepted

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

print(*l)


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


insertionsort(l, n)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
print(" ".join(map(str,a)))
def insertsort(m,b):
    j = 1
    while j <= m - 1:
        for t in range(0,j):
            if b[t] > b[j]:
                b[t],b[j] = b[j],b[t]
        j += 1
        print(" ".join(map(str,b)))

insertsort(n,a)

Submission status: Accepted

Solution code:
def insertionSort(self,len):
    for i in range(1,len,1):
        print(*self)
        v = self[i] #2
        j = i - 1
        while j >= 0 and self[j] > v:
            self[j+1] = self[j]
            j-=1
            self[j+1] = v
    print(*self)
numslen = int(input())
nums = [int(e) for e in input().split()]
insertionSort(nums,numslen)

Submission status: Accepted

Solution code:
def main():
  input()
  ary = list(map(int,input().split()))

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

if __name__ == '__main__':
  main()

Submission status: Accepted

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


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