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 = [int(x) for x in input().split()]

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

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

        else :
            break

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

Submission status: Accepted

Solution code:
num = int(input())
num_list = list(map(int, input().split(" ")))
for x in range(len(num_list)):
    if x == len(num_list) - 1:
        print(num_list[x])
    else:
        print(num_list[x],end=" ")

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

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
print(' '.join(map(str, A)))
#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)))

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:
def main():
    n = int(input())
    nums = input()
    print(nums)
    nums = nums.split(' ')
    nums = [int(i) for i in nums]
    insertion_sort(n, nums)


def insertion_sort(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(' '.join([str(i) for i in a]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#挿入ソート
#A[i] i = 1-n　でソート済み箇所をiで指定
#A[j] j = 0-i　でA[i]より大きな値が出てくるまで走査

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

Submission status: Accepted

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

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

lst2 = insertionSort(lst,N)

Submission status: Accepted

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

for i in range(N):
    if i==N-1:
        print(S[i])
    else:
        print(S[i],end=' ')

for i in range(1,N):
    key = S[i]
    if key < max(S[0:i]):
        S.pop(i)
        x = 0
        for k in range(i):
            if x==1:
                continue
            if key < S[k]:
                S.insert(k,key)
                x += 1
    
    for k in range(N):
        if k==N-1:
            print(S[k])
        else:
            print(S[k],end=' ')

Submission status: Accepted

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

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

print(' '.join(str(x) for x in L))

Submission status: Accepted

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


print(" ".join([str(a) for a in A]))

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

def show_step(A):
    ans = str(A[0])
    for a in A[1:]:
        ans += " "+str(a)
    print(ans)

show_step(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
    show_step(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)))
    temp = A[i]
    j = i - 1
    while A[j] > temp and j >= 0:
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = temp
print(' '.join(map(str, A)))

Submission status: Accepted

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

for i in range(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(map(str, nums)))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

def print_data(data):
    last_index = len(data) - 1
    
    for idx, item in enumerate(data):
        print(item, end='')
        if idx != last_index:
            print(' ', end='')

    print('')
        
def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    nowmax = -1
    result = []
    for i in range(N):
        if A_list[i] >= nowmax:
            result.append(A_list[i])
            nowmax = A_list[i]
        else:
            junban = []
            for j in range(i):
                if A_list[i] < result[j]:
                    asa = result[:j]
                    junban = asa
                    junban.append(A_list[i])
                    junban += result[j:]
                    result = junban
                    break         
        shutu = result[:i+1] + A_list[i+1:]
        print_data(shutu)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

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

print(str(A).replace('[', '').replace(']', '').replace(',', ''))

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(str(A).replace('[', '').replace(']', '').replace(',', ''))

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 j >= 0 and a[j] > key:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = key
    print(" ".join([str(x) for x in a]))

Submission status: Accepted

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

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

Submission status: Accepted

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

for i in range(n):
    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:
a= int(input())
x =[int(z) for y, z in enumerate(input().split()) if y < a and z.isdigit()]
print(*x)
for i in range(1,a):
    key = x[i]
    j = i-1
    while j >= 0 and x[j] > key:
        x[j+1] = x[j]
        j -= 1
    x[j+1] = key
    print(*x)

Submission status: Accepted

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

def show(A):
    for t in range(len(A)):
        if t != N -1:
            print(number[t],'',end='')
        else:
            print(number[t])


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

show(number)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def print_list(nums):
    output = ""
    for i in nums:
        output += str(i) + ' '
    print(output[:-1])

from sys import stdin
N = int(input())
nums = list(map(lambda x:int(x), stdin.readline().split(' ')))
for i in range(1, N):
    print_list(nums)
    num = nums[i]
    for j in range(0, i):
        if nums[j] > num:
            nums.insert(j, num)
            del nums[i+1]
            break
print_list(nums)

Submission status: Accepted

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

for i in range(len(A)):
    while i > 0:
        if A[i] < A[i-1]:
            A[i], A[i-1] = A[i-1], A[i]
            i -= 1
        else:
            break
    print (" ".join([str(v) for v in A]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def insert_sort(arr):
    for index in range(1, len(arr)):
        insert(index, arr)

def insert(index, arr):
    tmp = arr[index]
    for i in range(index-1, -1, -1):
        if arr[i] > tmp:
            arr[i + 1] = arr[i]
            arr[i] = tmp
        else:
            arr[i + 1] = tmp
            break
    print(" ".join(map(str, arr)))

n = input()
# w = '5 2 4 6 1 3'
l = list(map(int, input().split()))
print(" ".join(map(str, l)))
insert_sort(l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def insertionSort(A,N):
    for i in range(1,N):
        v=A[i]
        j=i-1
        while (j>=0 and A[j]>v):
            c=A[j+1]
            A[j+1]=A[j]
            A[j]=c
            j-=1
        for i in range(len(A)):
            if i!=len(A)-1:
                print(A[i],end=" ")
            else:
                print(A[i])                
a=int(input())
b=list(map(int,input().split()))
for i in range(len(b)):
    if i!=len(b)-1:
        print(b[i],end=" ")
    else:
        print(b[i])   
insertionSort(b,a)

Submission status: Accepted

Solution code:
num = int(input())
list = list(map(int,input().split()))
list_str = []
for i in list:
    list_str.append(str(i))

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

Submission status: Accepted

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

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

print(*A)
insertion_sort(A,N)

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    n = int(input())
    numbers=[]
    numbers=list(map(int,input().split()))
    print(*numbers)
    for i in range(1,n):
        #key is numbers value.when starting numbers[1].
        key = numbers[i]
        #j is numbers startpoint.when starting 0.
        j=i-1
        while j>= 0 and numbers[j] > key:
            # insert key in back of numbers[j+1]
            numbers[j+1] = numbers[j]
            j-=1
        numbers[j+1]=key
        print(*numbers)

if __name__=="__main__":
    main()

Submission status: Accepted

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

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

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(map(str, A)))

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    insertion_sort(A, N)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
num = list(map(int, input().split()))
cnt = 1
print(" ".join(map(str,num)))
while cnt < len(num):
    for i in range(cnt, 0, -1):
        if num[i] < num[i-1]:
            num[i], num[i-1] = num[i-1], num[i]
    print(" ".join(map(str,num)))
    cnt+=1

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def insert_sort(A:list) -> list:
    for i in range(1, len(A)):
        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
    return A


if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().rstrip().split()))
    print(" ".join(list(map(str,insert_sort(A)))))

Submission status: Accepted

Solution code:
def insertionSort(A, N):
    for i in range(1, N):
        pri_lst(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

def pri_lst(A):
    print(" ".join(map(str,A)))

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

insertionSort(A, N)
pri_lst(A)

Submission status: Accepted

Solution code:
def Insert_sort(array,N):
    for i in range(1,N):
        temp = array[i]
        j = i - 1
        print(*array)
        while(j >= 0 ) and (array[j] >= temp):
            array[j+1] = array[j]
            
            j -= 1
        array[j+1] = temp
    print(*array)      
            
    #array= ' '.join(array)
    
    
try:
    N = int(input())
    array = list(map(int,input().split()))
except ValueError as N:
    print('数値以外が入力されました')

Insert_sort(array,N)

Submission status: Accepted

Solution code:
#入力
n = int(input())
elements = [int(n) for n in input().split()]
print(' '.join(map(str, elements)))

#未ソート部分の先頭を取り出す
for i in range(1,n):
    v = elements[i]
    j = i - 1
    #ソート部分から挿入場所を決定する。
    while j >= 0 and elements[j] > v :
        elements[j+1] = elements[j]
        j -= 1
    elements[j+1] = v
    print(' '.join(map(str, elements)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
_ = input()

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

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

Submission status: Accepted

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


_N = int(input())
_A = list(input().split())
_A = [int(x) for x in _A]
insertion_sort(_A, _N)

Submission status: Accepted

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


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
        print(" ".join([str(a) for a in A]))


def main():
    _ = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    insertionSort(A)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, *aa = map(int, open(0).read().split())

for i in range(n):
    j = i
    while j-1 >= 0:
        if aa[j-1] > aa[j]:
            aa[j-1], aa[j] = aa[j], aa[j-1]
        j -= 1
    print(*aa)

Submission status: Accepted

Solution code:
# incert sort
N = int(input())
list_num = list(map(int, input().split(" ")))
print(" ".join(map(str, list_num)))

for i_incert in range(1, N):
    num_incert = list_num[i_incert]
    i_cmpr = i_incert - 1
    
    while i_cmpr >= 0 and list_num[i_cmpr] > num_incert:
        list_num[i_cmpr + 1] = list_num[i_cmpr]  # 一つ右にcopy(元のはnum_incertとして保持済)
        i_cmpr -= 1
    list_num[i_cmpr + 1] = num_incert
    print(" ".join(map(str, list_num)))

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

Submission status: Accepted

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

for i in range(N):
    v = A[i]
    if v >= A[0]:
        j = 0
        while v >= A[j] and j < i:
            j = j + 1
        if j < i:
            for k in reversed(range(j, i)):
                A[k + 1] = A[k]
            A[j] = v
            print(' '.join([str(a) for a in A]))
        else:
            print(' '.join([str(a) for a in A]))

    else:
        for l in reversed(range(i)):
            A[l+1]=A[l]
        A[0]=v
        print(' '.join([str(a) for a in A]))

Submission status: Accepted

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

for idx1 in range(len(nums)):
    num  = nums[idx1]
    idx2 = idx1 - 1
    while idx2 >= 0 and nums[idx2] > num:
        nums[idx2 + 1] = nums[idx2]
        idx2 -= 1
    nums[idx2+1] = num
    print(" ".join(map(str, nums)))

Submission status: Accepted

Solution code:
def insertion_sort(A):
    for i in range(1, len(A)):
        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(list(map(str,A))))

if __name__ == '__main__':
    n = int(input())
    l = list(map(int, input().split()))
    print(' '.join(list(map(str,l))))
    insertion_sort(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,sep=' ')

Submission status: Accepted

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

for i in range(n):
    b = sorted(a[:i+1])
    b.extend(a[i+1:])
    print(' '.join([str(i) for i in b]))

Submission status: Accepted

Solution code:
def insertionSort(arr): 
  
    # Traverse through 1 to len(arr) 
    for i in range(1, len(arr)): 
  
        key = arr[i] 
        j = i - 1
        
        while j >=0 and key < arr[j] : 
                arr[j+1] = arr[j] 
                j -= 1
        arr[j+1] = key
        
        print(' '.join(map(str, numbers)))

_ = input()
numbers = list(map(int, input().split()))
print(' '.join(map(str, numbers)))
insertionSort(numbers)

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

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

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 main():
    card_num = int(input())
    cards = list(map(int, input().split()))
    
    res = " ".join([str(n) for n in cards])
    print(res)
    
    for i in range(1, card_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
        
        res = " ".join([str(n) for n in cards])
        print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]

for i in range(1, n + 1):
    print(*A)
    if i >= n: break

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

        A[j+1] = v

    show(A)

def show(lst):
    print(*lst)


insertionSort(nums, N)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def InsertionSort(A, N=1):
    N = min(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
    return A


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

for i in range(len(a)):
    print(' '.join(map(str, InsertionSort(a, i+1))))

Submission status: Accepted

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

ans=str(num_list[0])
for k in range(1,len(num_list)):
    ans+=" "+str(num_list[k])
print(ans)

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

    ans=str(num_list[0])
    for k in range(1,len(num_list)):
        ans+=" "+str(num_list[k])
    print(ans)

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

Submission status: Accepted

Solution code:

test_case_1_num = int(input())
test_case_1 = list(map(int,input().split()))

print(" ".join(map(str, test_case_1)))
for i in range(1, test_case_1_num):
    t = test_case_1[i]
    p = i
    for j in range(0, i):
        if t > test_case_1[j]:
            continue
        else:
            for k in reversed(range(j,i)):
                test_case_1[k + 1] = test_case_1[k]
                p -= 1
            break

    test_case_1[p] = t

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

Submission status: Accepted

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

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

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

main()

Submission status: Accepted

Solution code:
def show(a):
    ans=""
    for c in a:
        if c==a[-1]:
            ans+=str(c)
        else:    
            ans+=str(c)+" "
    print(ans)

def insertionsort(a,n):
    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]
            j-=1
        a[j+1]=v
        show(a)

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

Submission status: Accepted

Solution code:
from sys import stdin


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

def main():
    read = stdin.readline
    N = int(read())
    data = list(map(int, read().split(" ")))
    for j in range(N-1):
        print(data[j], end=" ", sep=" ")
    print(data[N-1])
    insertion_sort(data, N)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    for i in range(N):
        v = A[i]
        j = i - 1
        while 0 <= j 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()))

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

Submission status: Accepted

Solution code:
#ALDS1_1_A:   Insertion Sort

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

for x in a:
    if x == a[n-1]:
        print(x)
    else:
        print(x, end=' ')

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split(" ")))
print(" ".join(list(map(str,A))))
for i in range(1,N):
    tmp=A[i]
    j=i-1
    while(j>=0 and A[j]>tmp):
        A[j+1]=A[j]
        j-=1
    A[j+1]=tmp
    print(" ".join(list(map(str,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
        print(*A)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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