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

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

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 v < A[j] and j >= 0:
        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()))

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)

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

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

Solution (Python):


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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):
def insertionSort(self,len):
    for i in range(1,len,1):
        print(*self)
        v = self[i] 
        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)

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

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

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




for i in range(1, N):
    print(*li)
    v = li[i]
    for j in reversed(range(0, i)):
        if li[j] > v:
            li[j + 1] = li[j]
            li[j] = v
        else:
            break

print(*li)

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

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

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

insertSort(int(input()), [int(i) for i in input().split()])

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):
N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    print(*A)
    for j in range(i):
        if A[j] > A[i]:
            break
    else:
        continue
    tmp = A[i]
    for k in range(i, j, -1):
        A[k] = A[k - 1]
    A[j] = tmp
print(*A)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
print(*a)
for i in range(1,n):
    for j in range(i):
        p = i-j
        if a[p] < a[p-1]:
             a[p], a[p-1] = a[p-1], a[p]
    print (*a)

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

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

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

def insertion(a:list, n:int) -> None:
    if not isinstance(a, list):
        return None

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

insertion(a, n)

Solution (Python):
import sys
input = sys.stdin.readline

def print_vec(vec):
    print(" ".join(map(str, vec)))

N = int(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_vec(A)

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

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

for i in range(len(nums)):
    num = nums[i]
    j = i - 1
    while j >= 0 and nums[j] > num:
        nums[j + 1] = nums[j]
        j -= 1
    nums[j + 1] = num

    print(*nums)

Solution (Python):
N = int(input())
data = list(map(int, input().split()))
    
for i in range(N):
    tmp = data[i]
    j = i - 1
    while j >= 0 and data[j] > tmp:
        data[j+1] = data[j]
        j -= 1
    data[j+1] = tmp
    
    for j in range(N):
        print("%d" %(data[j]), end="")
        if j != N-1:
            print(" ", end="")
    print()

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

print(*a)
for i in range(1,n):
    for j in range(i,0,-1):
        if a[j]<a[j-1]:
            a[j], a[j-1] = a[j-1], a[j]
    print(*a)

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

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

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

a = insertionSort(A[:], N)
print(' '.join(map(str, a)))

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

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

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

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

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

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

Solution (Python):
N = int(input())
num_list = [int(item) for item in input().split()]

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

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

        print(*A)

insertionSort(num_list, N)

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

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

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

insertsort(A,N)

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

print(" ".join([str(i) for i in a]))
for i in range(1, n, 1):
    for j in range(i):
        if a[i] < a[j]:
            a.insert(j, a[i])
            a.pop(i+1)
    print(" ".join([str(i) for i in a]))

Solution (Python):
N, *A = map(int, open(0).read().split())
print(' '.join([str(a) for a in A]))
for i in range(1, N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j + 1] = A[j]
        j -= 1
    A[j+1] = v
    print(' '.join([str(a) for a in A]))

Solution (Python):
n = int(input())
A = [int(s) for s 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):
import sys

def insertionSort(A, N):
    print(' '.join(map(str, A)))
    for i in range(1, N):
        v = A[i]
        j = i-1

        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j-=1
        A[j+1] = v
        print(' '.join(map(str, A)))

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

insertionSort(A, N)

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

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

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

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

    insertionSort(A, N)


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


main()

Solution (Python):
N = int(input())
A = input().split()
print(" ".join(A))
A = [int(l) for l 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
    A = [str(l) for l in A]
    print(" ".join(A))
    A = [int(l) for l in A]

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

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

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

Solution (Python):

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

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

InsertionSort(A, N)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
print(' '.join([str(a) for a in A]))

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

Solution (Python):
num = int(input())
an = [ int(i) for i in input().split()]
print(" ".join([str(n) for n in an]))

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

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

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
print(" ".join([str(a) for a in A]))

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

Solution (Python):
def InsertionSort(seq):
    print(*seq)
    for i in range(len(seq) - 1):
        j = i

        while j >= 0:
            if seq[j + 1] < seq[j]:
                seq[j + 1], seq[j] = seq[j], seq[j + 1]
                
            j -= 1 

        print(*seq)

def main():
    n = int(input())
    seq = [int(a) for a in input().split()]
    InsertionSort(seq)

main()

Solution (Python):

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


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


insertionSort(input_A, input_N)

Solution (Python):





def InsertionSort(A: list):
    for i in range(1, len(A)):
        key = A[i]
        j = i - 1
        print(*A, sep=" ")
        while (j >= 0 and A[j] > key):
            A[j+1] = A[j]
            j -= 1
        A[j+1] = key


def main():
    length = int(input())
    A = [int(e) for e in input().split(" ")]

    InsertionSort(A)
    print(*A, sep=" ")


if __name__ == "__main__":
    main()

Solution (Python):

n = int(input().rstrip())
data = list(map(int,input().split()))


for i in range(1, n):
    for s in range(n):
        if s != n-1:
            print(data[s], end=" ")
        else:
            print(data[s])
    min = i
    j = i-1
    while j >= 0:
        if data[min] < data[j]:
            tmp = data[j]
            data[j] = data[min]
            data[min] = tmp
            min = j
        j -= 1

for s in range(n):
    if s != n - 1:
        print(data[s], end=" ")
    else:
        print(data[s])

Solution (Python):
def show(A):
    N = len(A)
    for i in range(N):
        if i :
            print(' ', end = '')
        print(A[i], end = '')
    print()

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

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

insertionSort(A, N)

Solution (Python):
def printData(data) :
    for i, value in enumerate(data) :
        if i > 0 :
            print(" ", end = "")
        print(value, end = "")
    print()
    
def insertionSort(data, N) :
    for i in range(1, N) :
        target = data[i]
        j = i -1
        while j >= 0 and target < data[j] :
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = target
        printData(data)
        
N = int(input())
data = [int(char) for char in input().split()]
printData(data)
insertionSort(data, N)

Solution (Python):
def main1():
    N = int(input())
    A = [int(_) for _ 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)))
        
main1()

Solution (Python):

n = int(input())
numbers = input().split()

numbers = [int(num) for num in numbers]

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

for i in range(1, n):
    show(numbers)
    key = numbers[i]
    j = i - 1
    while j >= 0 and numbers[j] > key:
        numbers[j+1] = numbers[j]
        j -= 1

    numbers[j+1] = key
show(numbers)

Solution (Python):
x = int(input())
l_t = [int(i)for i in input().split()]
print(' '.join([str(p) for p in l_t]))
for i in range(1,x):
    v = l_t[i]
    j = i - 1
    while j >= 0 and l_t[j] > v:
        l_t[j + 1] = l_t[j]
        j = j - 1
    l_t[j + 1] = v
    print(' '.join([str(p) for p in l_t]))

Solution (Python):
def insertionSort(A, N): 
    for i in range(1, N):
        print(' '.join([str(p) for p 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(p) for p in A]))
        
n = int(input())
a_list = [int(i) for i in input().split()]
insertionSort(a_list, n)

Solution (Python):


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

print(*A)

for i in range(1,n):
    j = i
    while(j > 0):
        if A[j-1] > A[j]:
            A[j-1],A[j] = A[j],A[j-1] 
            j -= 1
        else:
            break
    
    print(*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 = 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):

def InsertionSort(A):
    i = 0
    j = 0
    print(' '.join([str(x) for x in A]))
    for i in range(1, N):
        movenum = A[i]
        j = i - 1
        while j >= 0 and movenum < A[j] : 
            
            A[j+1] = A[j]
        
            j -= 1

        A[j + 1] = movenum
        print(' '.join([str(x) for x in A]))

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

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

Solution (Python):
N = int(input())
li = list(map(int,input().split()))
print(*li)

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

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 = list(map(int, input().split()))
s = ''
for a in A:
    s += str(a) + ' '
print(s.rstrip())

for i in range(1, N):
    for j in range(0, i):
        if A[i] < A[j]:
            A.insert(j, A.pop(i))
            break
    s = ''
    for a in A:
        s += str(a) + ' '
    print(s.rstrip())

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

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

insertion_sort(a=a, n=n)


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

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
for i, a in enumerate(A):
    temp = a
    i -= 1
    while i >= 0 and A[i] >temp:
        A[i+1] = A[i]
        A[i] = temp
        i -= 1
    L=[str(a) for a in A]   
    p = ' '.join(L)
    print(p)

Solution (Python):
def InsertionSort(A, N):
    for i in range(N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        for j in range(N):
            if j == N-1:
                print(A[j])
            else:
                print(A[j], end=' ')
    return(A)

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

InsertionSort(A,N)