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: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if __name__ == "__main__":
    import sys
    N = int(sys.stdin.readline().strip())
    A = [ int(e) for e in sys.stdin.readline().strip().split() ]
    insertion_sort(A, N)

Submission status: Time Limit Exceeded

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

if N == 1:
    print(A[0])
else:

    for i in range(N):
        j = i

        while j > 0 and A[j] < A[j-1]:
            if A[j] > A[j-1]:

                break
                k = A[j]
                l = A[j-1]
                A[j-1] = k
                A[j] = l
                j -= 1

            S = str(A[0])
            for k in range(1,N-1):
                S += " " + str(A[k])

            S = S + " "+str(A[N-1])
            print(S)

Submission status: Accepted

Solution code:

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

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

insertionSort(a,n)

Submission status: Accepted

Solution code:
length=int(input())
firstArray=input()
listForArray=list(map(int,firstArray.split()))
listForPrint=[firstArray]


def insertionSort(list,length):
    index=1
    while index<length:
        if listForArray[index]<=listForArray[index-1]:
            for index2 in range(0,index):
                if listForArray[index2-1]<=listForArray[index] and listForArray[index]<=listForArray[index2] or index2==0 and listForArray[index]<=listForArray[index2]:
                    newCommer=listForArray[index]
                    n=index
                    while n>index2:
                        listForArray[n]=listForArray[n-1]
                        n-=1
                    listForArray[index2]=newCommer
                    break   
        nowArray=str(listForArray[0])
        for index3 in range(1,length):
            nowArray+=" "+str(listForArray[index3])
        listForPrint.append(nowArray)
        index+=1    
#---------------------main-------------------------
insertionSort(listForArray,length)
for array in listForPrint:
    print(array)

Submission status: Accepted

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

for i in range(0, len(a)) :
    repl = i
    cur_num = a[i]
    
    # fetch idx to replace
    for j in range(i, -1, -1) :
        if a[j] >= a[i] :
            repl = j
    
    # shift
    for k in range(i, repl - 1, -1) :
        a[k] = a[k - 1]
    
    a[repl] = cur_num
    
    print(" ".join(map(str, a)))

Submission status: Accepted

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


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

insertionSort(cards, number)

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
        B = A.copy()
        for t in range(N):
            B[t] = str(B[t])
        print(" ".join(B))


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:
def print_list(A):
    print(*A, sep=" ")

def insertion_sort(A, n):
    print_list(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_list(A)

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

insertion_sort(A, n)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    Mtx = list(map(int, input().split()))
    
    showMtx(Mtx)
    for i in range(1,n):
        for j in range(i,0,-1):
            if Mtx[j] < Mtx[j-1]:
                Mtx[j-1], Mtx[j] = Mtx[j], Mtx[j-1]
            # print(i, j, sep=', ')
        showMtx(Mtx)
                

def showMtx(Mtx):    
    q = len(Mtx)
    for i in range(q):
        if i != q - 1:
            print(Mtx[i], sep=' ', end=' ')
        else:
            print(Mtx[i])



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    Mtx = list(map(int, input().split()))
    
    showMtx(Mtx)
    for i in range(1,n):
        for j in range(i,0,-1):
            if Mtx[j] < Mtx[j-1]:
                Mtx[j-1], Mtx[j] = Mtx[j], Mtx[j-1]
            else:
                break
            # print(i, j, sep=', ')
        showMtx(Mtx)
                

def showMtx(Mtx):    
    q = len(Mtx)
    for i in range(q):
        if i != q - 1:
            print(Mtx[i], sep=' ', end=' ')
        else:
            print(Mtx[i])



if __name__ == '__main__':
    main()

Submission status: Accepted

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

def insertion_sort(lis, num):
    print(' '.join(map(str, lis)))
    for i in range(1, num):
        v = lis[i]
        j = i - 1  # j は iの前の数
        while j >= 0 and lis[j] > v:  # jが0以上で配列のj番目の要素が現在の要素より大きい場合
            lis[j + 1] = lis[j]  # 配列j+1番目の要素に配列j番目の要素を格納
            # print(' '.join(lis))
            j -= 1  # jを-1
            lis[j + 1] = v  # 配列j+1番目の要素にvを格納
        print(' '.join(map(str, lis)))
    return lis

insertion_sort(nums, n)

Submission status: Accepted

Solution code:
import sys

n = input()
sort_list = list()

sort_list = map(int, raw_input().split())

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

    sort_list[j+1] = tmp


    for k in range(0,n):
        sys.stdout.write(str(sort_list[k]))
        if k is not n - 1:
            sys.stdout.write(" ")
        elif i is not n - 1:
            sys.stdout.write("\n")
            
print("")

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

for i in range(n):
    for j in range(i):
        if a[j] > a[i]:
            a.insert(j, a[i])
            a.pop(i+1)
            break
    show(a)

Submission status: Accepted

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

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

n = int(input())
a = [int(i) for i in input().split()]
insertion_sort(a)
print(" ".join(map(str, a)))

Submission status: Accepted

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

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

n = int(input())
a = [int(i) for i in input().split()]
insertion_sort(a)
print(" ".join(map(str, a)))

Submission status: Accepted

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

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:
def insertion_sort(a, n):
    for i in range(1, n):
        v = a[i]
        j = i - 1
        while j >= 0 and a[j] > v:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        print(' '.join([str(i) for i in a]))


n = int(input())
a = [int(i) for i in input().split()]
print(' '.join([str(i) for i in a]))

insertion_sort(a, n)

Submission status: Accepted

Solution code:
# coding: utf-8

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def insert_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 = [int(n) for n in input().split()]; print(*A)
insert_sort(A, N)

Submission status: Accepted

Solution code:
# inputList = list(map(int, '''6
# 5 2 4 6 1 3'''.split()))
# N = inputList.pop(0)


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


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

            j-=1
        A[j+1] = v
        formatting(A)


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

formatting(inputList)
insertionSort(inputList, N)

Submission status: Accepted

Solution code:
input()
myarr = list(map(int, input().split()))
for i in range(len(myarr)):
    for j in range(i, 0,-1):
        if myarr[j] < myarr[j-1]:
            t = myarr[j]
            myarr[j] = myarr[j-1]
            myarr[j-1] = t
        else:
            break
    print(" ".join(map(str, myarr)))

Submission status: Accepted

Solution code:
# 配列の要素数
num = int(input())

# 配列
array = list(map(int, input().split()))

def print_array():
    for i in range(num):
        if i != num-1:
            print(array[i], end=' ')
        else:
            print(array[i])


# insertion sort
for i in range(num):
    insert = array[i]
    j = 0
    while array[j] < insert:
        j+=1
    for k in range(i, j, -1):
        array[k] = array[k - 1]
    array[j] = insert
    print_array()

Submission status: Accepted

Solution code:
num=int(raw_input().strip())

lst=map(int,raw_input().strip().split())
def sort(lst,idx):
    tmp=lst[idx]
    idx-=1
    while idx>=0 and lst[idx]>tmp:
        lst[idx+1]=lst[idx]
        idx-=1
    lst[idx+1]=tmp

for ii in xrange(num):
    sort(lst,ii)
    print " ".join(str(i) for i in lst)

Submission status: Accepted

Solution code:
def insertion_sort(A, N):
    yield 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
        yield A

N = int(input())
A = list(map(int, input().split()))
for li in insertion_sort(A, N):
    print(*li)

Submission status: Accepted

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


for i in range(N):
    if N == 1:
        print(A[0])
        break
    j = i

    while j > 0 and A[j] < A[j-1]:
        if A[j] > A[j-1]:

            break
        k = A[j]
        l = A[j-1]
        A[j-1] = k
        A[j] = l
        j -= 1

    S = str(A[0])
    for k in range(1,N-1):
        S += " " + str(A[k])

    S = S + " "+str(A[N-1])
    print(S)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int, input().split()))
k=list(map(str,a))
j=' '.join(k)
print(j)
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
    b=list(map(str, a))
    c=' '.join(b)
    print(c)

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(i) for i in input().split()]
S=""
for i in range(N-1):
    S=S+str(A[i])+" "
S=S+str(A[N-1])
print(S)
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
    S=""
    for i in range(N-1):
        S=S+str(A[i])+" "
    S=S+str(A[N-1])
    print(S)

Submission status: Accepted

Solution code:
def insertionSort(a, n):
    trace(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
        trace(a, n)


def trace(a, n):
    output = ''
    for i in a:
        if i == a[n-1]:
            output += str(i)
        else:
            output += str(i) + ' '
    print(output)

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

Submission status: Accepted

Solution code:
def insertion_sort(arr):
    print(" ".join(map(str, arr)))
    for i in range(1,len(arr)):
        j = i
        while arr[j] < arr[j-1] and j > 0:
            arr[j-1], arr[j] = arr[j], arr[j-1]
            j -= 1
        print(" ".join(map(str, arr)))

input()
arr = list(map(int, input().split()))
insertion_sort(arr)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    _ = input()
    array = [int(x) for x in input().split()]
    print(" ".join(map(str, array)))

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


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def showList(A, N):
    for i in range(N-1):
        print(A[i],end=' ')
    print(A[N-1])

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


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

A = 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:
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
        show(A)
        
     
def show(nums):
    for i in range(len(nums)):
        if i != len(nums) - 1:
            print(nums[i],end=' ')
        else:
            print(nums[i])
A = []
N = int(input())
A = list(map(int,input().split()))

show(A)
insertionSort(A,N)

Submission status: Accepted

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

def trace(a):
    a = map(str, a)
    print(' '.join(a))

def insertion(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
        trace(a)
    


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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def out(data) -> str:
    print(' '.join(map(str, data)))


N = int(input())
data = [int(i) for i in input().split()]
out(data)
for i in range(1, 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
    out(data)

Submission status: Accepted

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

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

        string = list(map(str, A))
        print(' '.join(string))

insertion_sort(A, N)

Submission status: Accepted

Solution code:
from sys import stdin
 
n = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().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 = j-1
    else:
        A[j+1] = v
        print(*A)

Submission status: Accepted

Solution code:
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):
    j = i
    while a[j - 1] > a[j] and j > 0:
        a[j], a[j - 1] = a[j - 1], a[j]
        j -= 1
    print(" ".join([str(i) for i in 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):
    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(map(str, 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(' '.join(map(str, a)))

Submission status: Accepted

Solution code:
def inserrtionsort(l,n):
  for i in range(1,n):
    print(" ".join(l))
    v=l[i]
    j=i-1
    while int(v)<int(l[j]) and j>=0:
      l[j+1]=l[j]
      j-=1
    l[j+1]=v
  print(" ".join(l))
m=int(input())
n=list(input().split())
inserrtionsort(n,m)

Submission status: Accepted

Solution code:
n = int(input())

data = input().split()

array = []

for i in data:
  array.append(int(i))

for i in range(1, n):
  print(*array)

  key = array[i]

  j = i - 1

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

  array[j+1] = key 

print(*array)

Submission status: Accepted

Solution code:
# -*- Coding: utf-8 -*-
def trace(A, N):
    for i in range(int(N)-1):
        print(A[i], end=' ')
    print(A[int(N)-1])

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

if __name__ == '__main__':
    N = input()
    A = list(map(int, input().split()))
    
    trace(A, N)
    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())
arr=list(map(int,input().split()))
print(' '.join(map(str,arr)))
for i in range(1,n):
  v=arr[i]
  j=i-1
  while j>=0 and arr[j]>v:
    arr[j+1]=arr[j]
    j-=1
  arr[j+1]=v
  print(' '.join(map(str,arr)))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

	#出力用
	list2 = [str(k) for k in A]
	print(" ".join(list2))

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

        outputNum(A)

def outputNum(A):
    tmp = map(str,A)
    text = " ".join(tmp)
    print(text)

outputNum(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(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())
l = list(map(int, input().split()))
print(" ".join(map(str,l)))
def insertionSort(a, 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]#a[i]の位置に詰めていく処理
            j -= 1
        a[j+1] = v
        print(" ".join(map(str,a)))#１行ごとに出力
insertionSort(l,n)

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

Submission status: Accepted

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

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

    print(*L)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def sort(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
        pr(A)

def pr(list):
    n = len(list)
    for i in range(n):
        if i < n-1:
            print(list[i],end=" ")
        else:
            print(list[i],end="\n")

sort(N,A)

Submission status: Accepted

Solution code:

def insertionSort(S, N):
    for i in range(N):
        v = S[i]
        j = i-1
        while j >= 0 and S[j] > v:
            S[j+1] = S[j]
            j = j-1
        S[j+1] = v
        
        print(' '.join(map(str, S)))
        
        
n = int(input())
s = list(map(int, input().split()))
insertionSort(s, n)

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:
# coding:utf-8

def printline(data):
    l=""
    for i,s in enumerate(data):
        l = l + str(s)
        if i+1 != len(data):
            l = l+" "
    print(l)


length = int(input())
data = list(map(int,input().split()))
printline(data)
for i in range(1,len(data)):
    tmp = data[i]
    i2 = i - 1
    while i2 >=0 and data[i2] > tmp:
        data[i2+1] = data[i2]
        i2 -= 1

    data[i2+1] = tmp
    printline(data)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
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(*A, sep=" ")

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

Submission status: Accepted

Solution code:
def insertion_sort(A):
    n = len(A)
    print(*A)
    for i in range(1, n):
        item = A[i]
        cur_idx = i - 1
        while cur_idx >= 0 and A[cur_idx] > item:
            A[cur_idx], A[cur_idx + 1] = A[cur_idx + 1], A[cur_idx]
            cur_idx -= 1
        print(*A)


if __name__ == "__main__":
    N = int(input())
    A = [int(elem) for elem in input().split()]
    insertion_sort(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):
    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(map(str,A)))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    number = int(raw_input())
    list = map(int, raw_input().split())
    sort(number, list)

def sort(number, list):
    output(list)
    for i in range(1, number):
        key = list[i]
        j = i - 1
        while j >= 0 and list[j] > key:
            list[j+1] = list[j]
            j -= 1
        list[j+1] = key
        output(list)

def output(list):
    print(" ".join(map(str, list)))

main()

Submission status: Accepted

Solution code:
n = input()
a = map(int, raw_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)))

Submission status: Accepted

Solution code:
N = input();
A = map(int,raw_input().split(" "))
for i in range(1,len(A)):
	key = A[i]
	j = i - 1;
	for k in range(0,len(A)):
		if A[N-1] == A[k]:
			print A[k]
		else:
			print A[k],
	while j >=0 and A[j] > key:
		A[j+1] = A[j]
		j -= 1
	A[j+1] = key
for j in range(0,len(A)):
		if A[N-1] == A[j] :
			print A[j]
		else:
			print A[j],

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = raw_input()

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

for i, key in enumerate(A):

    j = i - 1

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

    A[j+1] = key

    for x in A:
        print x,
    print