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:
import sys
import math

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

for i in xrange(n) :
    tmp = a[i]
    a.pop(i)

    for j in xrange(i) :
        if a[j] > tmp :
            a.insert(j, tmp)
            break
    else :
        a.insert(i, tmp)

    for j in xrange(n) :
        sys.stdout.write(str(a[j]))
        if j < n-1 :
            sys.stdout.write(" ")

    print

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A

num = int(input())

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

for i in list(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())
arr = []
s = input().split()
for i in range(n):
    arr.append(int(s[i]))
for i in range(n):
    k = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > k:
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = k
    for i in range(n):
        if i == n-1:
            print(arr[i])
        else:
            print(arr[i], end=" ")

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = 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) & (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 ins(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 k in range(len(A)):
			if k==len(A)-1:
				print(A[k])
			else:
				print(A[k],end=" ")
N=int(input())
A=list(map(int,input().split(" ")))
ins(A,N)

Submission status: Accepted

Solution code:
#-*- coding: utf-8 -*-


def insertion_sort(A):
    print ' '.join(map(str, A))
    for i in xrange(1, 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
        print ' '.join(map(str, A))
    return A


if __name__ == "__main__":
    N = input()
    A = map(int, raw_input().split())
    result = insertion_sort(A)

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys


def main():
  length = int(input())
  elements = list(map(int, input().split()))
  print(" ".join(str(i) for i in elements))

  sorted_list = [elements[0]]
  for i in range(1, length):
    element = elements[i]
    for j in range(0, len(sorted_list) + 1):
      if j == len(sorted_list):
        sorted_list.append(element)
      elif element < sorted_list[j]:
        sorted_list.insert(j, element)
        break
    output_list = sorted_list[0:i+1] + elements[i+1:]
    print(" ".join([str(i) for i in output_list]))

  return 0

if __name__ == '__main__':
  main()

Submission status: Accepted

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

#for i in range(n):
#    A[i] = int(A[i])
print(" ".join(A))

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

    while j >= 0 and int(A[j]) > int(v):
        A[j+1] = A[j]
        j -= 1
        A[j+1] = v
    print(" ".join(A))

Submission status: Accepted

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

#for i in range(n):
#    A[i] = int(A[i])
print(" ".join(A))

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

    while j >= 0 and int(A[j]) > int(v):
        A[j+1] = A[j]
        A[j] = v
        j -= 1
    print(" ".join(A))

Submission status: Accepted

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

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

insertionSort(A, N)

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

Submission status: Accepted

Solution code:
def Print(numlist):
	for t in range(len(numlist)):
		print(numlist[t], end = '')
		if t != len(numlist) - 1:
			print(end = ' ')
	print()

n = eval(input())
numlist = [eval(item) for item in input().split()]
Print(numlist)
for i in range(1, n):
	tmp = numlist[i]
	for j in range(i, -1, -1):
		if tmp > numlist[j - 1]:
			break
		numlist[j] = numlist[j - 1]
	numlist[j] = tmp
	Print(numlist)

Submission status: Accepted

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

def print_array(array):
     print(str(array)[1:-1].replace(', ', ' '))


def main():
    N = int(input())
    array = [int(s) for s in input().split(' ')]
    insertion_sort(array)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, 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
    
    print(" ".join(map(str, A)))

Submission status: Accepted

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

print(' '.join([str(item) for item 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 = j - 1
    A[j+1] = key
    print(' '.join([str(item) for item in A]))

Submission status: Accepted

Solution code:
length = int(input())
targ = [int(n) for n in input().split(' ')]
for l in range(length):
    for m in range(l):
        if targ[l - m] < targ[l - m - 1]:
            disp = targ[l-m -1]
            targ[l-m-1] = targ[l-m]
            targ[l-m] = disp
    print(" ".join([str(n) for n in targ]))

Submission status: Accepted

Solution code:
length = int(input())
targ = [int(n) for n in input().split(' ')]
for l in range(length):
    insert = 0
    for m in range(l):
        if targ[l] >= targ[l - m - 1]:
            insert = l - m
            break
    aftdisp = targ[l]
    for i in range(0,l - insert):
        disp = targ[l - i]
        targ[l - i] = targ[l - i - 1]
        targ[l - i - 1] = disp
    print(" ".join([str(n) for n in targ]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
_ = input()
A = [int(a) for a in input().split(" ")]
for i in range(1, len(A)):
  print(" ".join([str(a) for a in 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([str(a) for a in A]))

Submission status: Accepted

Solution code:
def show_list(num_list):
    for i in range(len(num_list)):
        print(str(num_list[i]), end="")
        if i < len(num_list)-1:
            print(" ", end="")
        else:
            print()

input_num = int(input())
num_list = [int(i) for i in input().split()]
show_list(num_list)
for i in range(1, len(num_list)):
    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
    show_list(num_list)

Submission status: Accepted

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

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

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(sys.stdin.readline().strip())
    data = [int(i) for i in sys.stdin.readline().strip().split(' ')]
    print_data(data)
    
    for i in range(1, n):
        v = data[i]
        j = i - 1

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

        data[j+1] = v
        print_data(data)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def insertionSort(_list, _length):
    for i in range(1, _length):
        ll = [str(_l) for _l in _list]
        print(' '.join(ll))
        val = _list[i]
        j = i - 1
        while j >= 0 and _list[j] > val:
            _list[j+1] = _list[j]
            j -= 1
        _list[j+1] = val
    ll = [str(_l) for _l in _list]
    print(' '.join(ll))


length = int(input())
eles = list(map(int, input().split()))

insertionSort(eles, length)

Submission status: Accepted

Solution code:
length = int(input())
eles = [int(i) for i in input().split()]

for i in range(length):
    val = eles[i]
    j = i - 1
    while j >= 0 and eles[j] > val:
        eles[j+1] = eles[j]
        j -= 1
    eles[j+1] = val
    print(*eles)

Submission status: Accepted

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

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

Submission status: Accepted

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

def main():
	N = int( raw_input() )
	A = map(int, raw_input().split())
	print " ".join(map(str, A))
	InsertionSort(A, N)

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
#coding:UTF-8
def IS(N,A):
    for i in range(int(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
        ans=""
        for k in range(len(A)):
            ans+=str(A[k])+" "
        print(ans[:-1])

if __name__=="__main__":
    N=input()
    a=input()
    A=a.split(" ")
    for i in range(len(A)):
        A[i]=int(A[i])
    IS(N,A)

Submission status: Accepted

Solution code:
n = int(raw_input())
A = map(int, raw_input().split(" "))

def printElem(B):
    string = ""
    for elem in B:
        string += str(elem) + " "
    print(string[:len(string)-1])

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

    printElem(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
 
        print(' '.join(map(str, A)))
 
if __name__ == "__main__":
    n = int(input())
    a = [int(e) for e in input().split()]
    print(' '.join(map(str, a)))
    insertionSort(a, n)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
num = int(raw_input())
line = raw_input()
 
item_str = line.strip().split(" ")
print " ".join(item_str)
A = map(int, item_str)
 
for i in range(1, num):
    v = A[i]
    j = i - 1
    for j in range(j, -1, -1):
        if A[j] > v:
            A[j+1] = A[j]
            j -= 1
        else:
            break
    A[j+1] = v
    str_A = map(str, A)
    print " ".join(str_A)

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
    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:
#!/usr/bin/env python
# encoding: utf-8

from __future__ import print_function


class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """

    @staticmethod
    def insertion_sort():
        # write your code here
        array_length = int(input())
        unsorted_array = [int(x) for x in input().split()]

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


if __name__ == '__main__':
    solution = Solution()
    solution.insertion_sort()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N = raw_input()
A =raw_input().split()
print ' '.join(map(str, A)) 
A = map(int, 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 = j - 1 
    A[j+1] = v 
    print ' '.join(map(str,A))

Submission status: Accepted

Solution code:
def insertionSort(length, numbers):
     for i in range(length):
          for k in range(length):
               if numbers[i] <= numbers[k]:
                    numbers.insert(k, numbers[i])
                    del numbers[i+1]
                    print ' '.join(map(str, numbers))
                    break
          

length = int(raw_input())
numbers = map(int, raw_input().split())


insertionSort(length, numbers)

Submission status: Accepted

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

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

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

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:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp
#?????\????????????????£?
#?¨?????????????????????????????????±?????????
def insertion_sort(target_list, n_list):
    
    for focus_index in range(1, n_list):
        print(*target_list)
        target = target_list[focus_index]
        if target < target_list[focus_index - 1]:#?????£?????°??????????????§??????
            compare_index = focus_index

            while compare_index > 0 and target_list[compare_index - 1] > target:
                target_list[compare_index] = target_list[compare_index - 1]
                compare_index -= 1;

            target_list[compare_index] = target
    
    return target_list

def main():
    n_list = int(input())
    target_list = [int(a) for a in input().split()]
    print(*insertion_sort(target_list, n_list))
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
implementation of the Insertion Sort
"""
number_of_input = int(raw_input())

numbers = [int(x) for x in raw_input().split()]

for i in range(1, len(numbers)):
    print " ".join([str(x) for x in numbers])
    target = numbers[i]
    index = i - 1
    while index >= 0 and target < numbers[index]:
        numbers[index + 1] = numbers[index]
        index -= 1
    numbers[index + 1] = target

print " ".join([str(x) for x in numbers])

Submission status: Accepted

Solution code:
"""
implementation of the Insertion Sort
"""
number_of_input = int(raw_input())

numbers = [int(x) for x in raw_input().split()]
print " ".join([str(x) for x in numbers])
for i in range(1, number_of_input):
    target = numbers[i]
    index = i - 1
    while index >= 0 and target < numbers[index]:
        numbers[index + 1] = numbers[index]
        index -= 1
    numbers[index + 1] = target
    print " ".join([str(x) for x in numbers])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

for m in range(N-1):
	print str(A[m]),
print A[N-1]

Submission status: Accepted

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

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

insertionSort(A)

Submission status: Accepted

Solution code:
def insertion_sort(array, debug=False):
    """ AOJ??¬??¶?????¬???
    http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_1_A

    :param array: ?????????????±??????????
    :param debug: ??????????????????????????????????????????????????°
    :return: ?????????????????????
    """
    for i in range(0, len(array)):  # i????¬??????????????????????????????????
        v = array[i]  # ?????¨?????\???????????¨????????????????????????????????´???
        j = i - 1
        while j >= 0 and array[j] > v:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = v
        if debug is True:
            print(' '.join(map(str, array)))
    return array


if __name__ == '__main__':
    # ??????????????¬?????¨
    # start_time = datetime.now()
    # print('>>> {0}'.format(start_time))

    # ??????????????\???
    num = int(input())
    data = [int(x) for x in input().split(' ')]
    # data = [5, 2, 4, 6, 1, 3]

    # ?????\??????????????????
    result = insertion_sort(data, debug=True)

    # ???????????????
    # print('result: {0}'.format(result))

Submission status: Accepted

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

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

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:
#! /usr/bin/env python
#-*- coding: utf-8 -*-

''' ?????\????????? '''

#
# ?¨??????????O()


def insertion_sort(A, N):

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

    return A


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    # N = 6
    # A = [5, 2, 4, 6, 1, 3]
    array_sorted = insertion_sort(A, N)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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

if __name__ == '__main__':
    n = int(input())
    a = [int(n) for n in input().split()]
    insertion_sort(a, n)

Submission status: Accepted

Solution code:
# -*- coding : utf-8 -*-

def insertion_sort(list):
    for i in range(1, len(list)):
        key = list[i]
        j = i - 1
        show_list(list)
        while(j >= 0 and list[j] > key):
            list[j+1] = list[j]
            j = j - 1
        list[j+1] = key
    show_list(list)
    return list

def show_list(list):
    i = 0;
    while(i < len(list)-1):
        print(list[i], end=" ")
        i = i + 1
    print(list[i])

list_length = int(input())
list = [int(x) for x in input().split(" ")]
insertion_sort(list)

Submission status: Accepted

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

n = int(input())
seq = list(map(int, input().split()))
insertion_sort(seq)

Submission status: Accepted

Solution code:
N = int(input())
#print(N)
card = list(map(int, input().split()))
#print(card)

for i in range(N):
    v = card[i]
    j = i - 1
    while j >= 0 and card[j] > v:
        card[j+1] = card[j]
        j = j -1
    card[j+1] = v
    #print(card)
    card_str = ""
    
    for k in range(N):
        card_str += str(card[k])
        card_str += " "
    
    print(card_str[:-1])

Submission status: Accepted

Solution code:
# coding: utf-8
n = int(input())
data = [int(i) for i in input().split()]

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

Submission status: Accepted

Solution code:

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

        # convert string to int.
        process_list = map(str, a)
        # join as string.
        print(" ".join(process_list))


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

insertion_sort(num_array, num_length)

Submission status: Accepted

Solution code:
#input number
n = raw_input()

if n < 1 and n > 100:
	exit()

# input elements
l = raw_input()

elements = [int(e) for e in l.split()]

print ' '.join(str(e) for e in elements)

for i in range(1, int(n)):
	key = elements[i]
	j = i - 1
	while j >= 0 and elements[j] > key:
		elements[j + 1] = elements[j]
		j -= 1
	elements[j + 1] = key
	# output
	print ' '.join(str(e) for e in elements)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def insertion_sort(seq, l):
    print(' '.join([str(n) for n in seq]))
    for i, v in enumerate(seq[1:], start=1):
        left = i - 1
        while left >= 0 and seq[left] > v:
            seq[left], seq[left+1] = seq[left+1], seq[left]
            left -= 1
        print(' '.join([str(n) for n in seq]))


def to_int(v):
    return int(v)


def to_seq(v):
    return [int(c) for c in v.split()]


if __name__ == '__main__':
    l = to_int(input())
    seq = to_seq(input())

    insertion_sort(seq, l)

Submission status: Accepted

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


# ?????\?????????
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)

print(*A)
insertion_sort(A, N)

Submission status: Accepted

Solution code:
debug = True

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
        if debug: print(*A)

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

print(*arr)
insertionSort(arr, n)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

import sys

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
    return A

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

for i in range(1,n+1):
    A = insertionSort(A,i)
    for l in range(len(A)):
        if l == len(A)-1:
            print(A[l])
            break
        print(A[l], end=' ')

Submission status: Accepted

Solution code:

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)

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

InsertionSort(A, N)

Submission status: Accepted

Solution code:
def insertion(A,n):
  for i in range(0,n):
    tmp = A[i]
    j = i - 1
    while(A[j] > tmp and j >= 0):
      A[j+1] = A[j]
      j-=1
    A[j+1] = tmp
    printList(A)


def printList(A):
  print(" ".join(str(x) for x in A))

n = int(input())
A = [int(x) for x in input().split()]
insertion(A,n)

Submission status: Accepted

Solution code:
def insertion_sort(target_list):
    sorted_list = list()
    for target in target_list[:]:
        for i, num in enumerate(sorted_list):
            if num > target:
                sorted_list[i:i] = [target]
                break
        else:
            sorted_list.append(target)
        target_list.pop(0)
        print(' '.join(str(s) for s in sorted_list + target_list))

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

Submission status: Accepted

Solution code:
def insert_sort(A):
    for i in range(1, len(A)):
        k = A[i]
        j = i - 1
        while j >= 0 and A[j] > k:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = k
        show(A)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    values = list(map(int,input().split()))
    for i in range(1,N):
        print(" ".join(map(str,values)))
        v = values[i]
        j = i - 1
        while 0 <= j and v < values[j]:
            values[j+1] = values[j]
            j -= 1
        values[j+1] = v
    print(" ".join(map(str, values)))


if __name__ == "__main__":
    import os
    import sys
    if len(sys.argv) > 1:
        if sys.argv[1] == "-d":
            fd = os.open("input.txt", os.O_RDONLY)
            os.dup2(fd, sys.stdin.fileno())
            main()
    else:
        main()