Problem:


Insertion Sort

Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

for i = 1 to A.length-1
    key = A[i]
    /* insert A[i] into the sorted sequence A[0,...,j-1] */
    j = i - 1
    while j >= 0 and A[j] > key
        A[j+1] = A[j]
        j--
    A[j+1] = key

Note that, indices for array elements are based on 0-origin.

To illustrate the algorithms, your program should trace intermediate result for each step.

Input

The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by a single space.

Output

The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space.

Constraints

1 ≤ N ≤ 100

Sample Input 1

6
5 2 4 6 1 3

Sample Output 1

5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3
1 2 3
1 2 3

Hint

Template in C



Sample input:
6
5 2 4 6 1 3


Sample output:
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

Submission status: Accepted

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


for i in range(N-1):
    j = i
    while True:
        if j == -1:
            break
        if A[j]>A[j+1]:
            v = A[j]
            A[j] = A[j+1]
            A[j+1] = v
        j += -1
        
    for x in range(N):
        if x == N-1:
            print(A[x])
        else:
            print(A[x],end=' ')

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
# import bisect
# import math
# import itertools
# import numpy as np
# import collections

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e, p = range, enumerate, print
    ip = IP()
    id = Idea()
    mod = 10 ** 9 + 7

    """この下から書いてね"""
    n = ip.I()
    a = ip.IL()
    p(*a)
    for i in r(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
        p(*a)


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
nums = list(map(int,input().split()))
print(" ".join(map(str,nums)))
for i in range(1,n): #未ソートの部分列の先頭を示すループ変数
    v = nums[i] #nums[i]の値を一時的に保持しておくための変数
    j = i - 1 #ソート済み部分列からvを挿入するための位置を探すループ変数
    while j >= 0 and nums[j] > v:
        nums[j+1] = nums[j] #jにあった数をj+1(つまりi)に移す
        j -= 1 #jの位置を下げて、Falseになるまで確認する
    nums[j+1] = v
    print(" ".join(map(str,nums)))

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):
    for j in range(i):
        if a[i] > a[i-j-1]:
            temp = a.pop(i)
            a.insert(i-j,temp)
            break
        elif j == i - 1:
            temp = a.pop(i)
            a.insert(0,temp)
    print(" ".join(map(str,a)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def show(nums):
    print(" ".join(list(map(str, nums))))


def insertion_sort(nums):
    show(nums)
    for i in range(1, len(nums)):
        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)


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

Submission status: Accepted

Solution code:
def pr(A):
    N = len(A);
    for i in range(N):
        if i :
            print (" ", end = "");
        print (A[i], end = "")
    print ("")

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

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

insertionSort(A)

Submission status: Accepted

Solution code:
N = int(input())

Line_A = list(map(int, 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(Line_A, N)

Submission status: Accepted

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

def insec_sort(A, N):

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

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

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


insec_sort(A,N)

Submission status: Accepted

Solution code:
N = int(input())
A = input().split()
print(' '.join(A))
A = [int(s) for s in A]
while A != sorted(A):
    for i in range(1, N):
        tmp = A[i]
        if A[i-1] > tmp:
            j = i
            while j >0 and A[j-1] > tmp:
                A[j] = A[j-1]
                j -= 1
            A[j] = tmp
        result = map(str, A)
        print(' '.join(result))

Submission status: Accepted

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

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

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

        show(nums)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
print(' '.join(map(str,a)))
for i in range(1,n):
    a_n=a.pop(i)
    insert_index = bisect.bisect_left(a[:i],a_n)
    a.insert(insert_index,a_n)
    print(' '.join(map(str,a)))

Submission status: Accepted

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


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


insertionSort(a)
print(" ".join([str(i) for i in 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:
N = int(input())
A = [int(i) for i in 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]
        A[j] = v
        j-=1
print(' '.join(map(str,A)))

Submission status: Accepted

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

for i in range(N):
    if i!=N-1:
        print(nums[i],end=' ')
    else:
        print(nums[i])
    
for i in range(1,N):
    key = nums[i]
    j =i-1
    while j >= 0 and nums[j] > key:
        nums[j+1] = nums[j]
        j-=1
    nums[j+1] = key
    
    for i in range(N):
        if i!=N-1:
            print(nums[i],end=' ')
        else:
            print(nums[i])

Submission status: Accepted

Solution code:
def readInt():
  return int(input())


def readInts():
  return [int(i) for i in input().split()]


N = readInt()
AS = readInts()

print(' '.join([str(i) for i in AS]))
for i, a in enumerate(AS[1:]):
    while i >= 0 and AS[i] > a:
        AS[i + 1] = AS[i]
        i -= 1
    AS[i + 1] = a
    print(' '.join([str(i) for i in AS]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solution(count,nums):
    for i in range(count):
        objNum = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > objNum:
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = objNum
        print(' '.join(map(str,nums)))



count = int(input())
tmp = input().split(" ")
nums = []
for i in tmp:
    nums.append(int(i))
solution(count,nums)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
*v, = map(int, input().split())
v = v[:n]

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

Submission status: Accepted

Solution code:
import sys

n = int(input())
nums = [int(num) for num in input().split(" ")]

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

        result = ""
        for k in range(0, n - 1):
            result += str(nums[k])
            result += " "
        result += str(nums[n - 1])
        print(result)

Submission status: Accepted

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

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

insertionSort(N,A)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
length = int(input())
raw_list = input().split()
for i in range(length):
	raw_list[i] = int(raw_list[i])
for i in range(length):
	key = raw_list[i]
	j = i - 1
	while j >= 0 and raw_list[j] > key:
		raw_list[j+1] = raw_list[j]
		j -= 1
	raw_list[j+1] = key
	for k in range(length):
		if k-length+1:
			print(raw_list[k], end=' ')
		else:
			print(raw_list[k])

Submission status: Accepted

Solution code:
def Show():
    print(' '.join([str(aa) for aa in a]))

n = int(input())
a = list(map(int, input().split()))
Show()
for i in range(1, n):
    target = a[i]
    j = i-1 
    while j >= 0 and a[j] > target:
        a[j+1] = a[j] 
        j -= 1
    a[j+1] = target
    Show()

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(list(map(str, a))))
n = int(input())
a = list(map(int, input().split()))
print(' '.join(list(map(str, a))))
insertionSort(a, n)

Submission status: Accepted

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

insertionSort(A, N)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
r = list(map(int,input().split()))
for i in range(n):
    value = r[i]
    while i >= 1 and r[i-1] > value:
        r[i] = r[i-1]
        i -= 1
    r[i] = value
    print(*r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def pres(data, N):
    for i in range(N):
        if i < N-1:
            print('%d '%data[i], end='')
        else:
            print(data[i])
        
def ins_sort(data, N):
    for i in range(1, N):
        flag = data[i]
        j = i-1
        while j>=0 and data[j]>flag:
            data[j+1] = data[j]
            j-=1
        data[j+1] = flag
        pres(data, N)
    
    
N = int(input())
data  = list(map(int, input().split()))

pres(data, N)
ins_sort(data, N)

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 = j - 1
        A[j + 1] = v
        print(' '.join(map(lambda x: str(x), A)))
    return A

N = input()

while True:
    try:
        line = raw_input()
        print(line)
        num_list = map(lambda x : int(x), line.strip().split())
        insertionSort(num_list, N)
    except EOFError:
        break

Submission status: Accepted

Solution code:
N = int(input()) #number of elements
seq = list(map(int,input().split()))
print(' '.join([str(i) for i in 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([str(k) for k in seq]))

Submission status: Accepted

Solution code:
# coding: utf-8

def printA(a, n):
    for i in range(n):
        print(a[i],end="")
        if i < n - 1:
            print(" ", end="")
        else:
            print()

def insertionSort(a, n):
    printA(ai, 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
        printA(ai, n)

num = int(input().rstrip())
ai = list(map(int,input().rstrip().split()))
insertionSort(ai, num)

Submission status: Accepted

Solution code:
def trace(A: list):
    print(*A)

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

    return A


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

trace(A)
insertionSort(A, 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())
A = list(map(int,input().split()))
show(A)
for i in range(1,N):
    v = A[i]
    while i - 1 >= 0 and A[i-1] > v:
        A[i] = A[i-1]
        i -= 1
    A[i] = v
    show(A)

Submission status: Accepted

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

def insertion_sort(array):
    putsarray(array)
    N = len(array)
    for i in range(1, N):
        j = i - 1
        num = array[i]
        while j >= 0 and array[j] > num:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = num
        putsarray(array)

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


N = int(input())
array = input().split()
array = [int(n) for n in array]
insertion_sort(array)

Submission status: Accepted

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

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

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=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 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(n):
  for j in range(1, n):
    if i-j >= 0 and a[i-j] > a[i-j+1]:
      a[i-j], a[i-j+1] = a[i-j+1], a[i-j]
    else:
      break
  print(" ".join([str(i) for i in a]))

Submission status: Accepted

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

ins(N, A)

Submission status: Accepted

Solution code:
def insertionSort(A, N):
    '''list of int, int(=len(A)) -> list of int
    return sorted list(insertion sort)
    '''
    l = N
    outA = A.copy()
    for i in range(l):
        val = outA[i]
        j = i - 1
        while j >= 0 and outA[j] > val:
            outA[j + 1] = outA[j]
            j -= 1
        outA[j + 1] = val
        printlist(outA)
    return outA
def printlist(L):
    '''
    print list with space
    '''
    for item in L[:-1]:
        print(item, end = ' ')
    print(L[-1])

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

Submission status: Accepted

Solution code:
num = int(input())

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

for i in range(1, num):
        temp = A[i]
        j = i - 1
        while j >= 0 and A[j] > temp:
                A[j + 1] = A[j]
                j -= 1
        A[j + 1] = temp
        tempA = map(str, A)
        print(' '.join(tempA))

Submission status: Accepted

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


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

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

insertion_sort(A)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


def printArrLine( arr ):
    print(' '.join(list(map(str,arr))))
    
def inputArrLine():
    return [int(i) for i in input().split()]
    
def insert( arr ):
    n = len(arr)
    printArrLine(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 = j-1
        arr[j+1] = v
        printArrLine(arr)

n = int(input())

ar = inputArrLine()

insert(ar)

Submission status: Accepted

Solution code:
def insertionSort(L, n):
  for i in range(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(' '.join(map(str, L)))

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:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 26 21:11:25 2019

@author: Yamazaki Kenichi
"""

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
print(" ".join(a))
a1 = [a[0]]
a2 = a[1:]
for _ in range(n - 1):
    for j, k in enumerate(a1):
        if int(a2[0]) < int(k):
            if j == 0:
                a1.insert(0, a2[0])
            else:
                a1.insert(j, a2[0])
            break
    else:
        a1.append(a2[0])
    del a2[0]
    print(" ".join(a1 + a2))

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 show(list1):
  for i in range(len(list1)):
    if i<len(list1)-1:
      print(list1[i],end=' ')
    else:
      print(list1[i])  # print() 默认以回车作为输入结束符

n = int(input()) # input()从标准输入读入一行文本
  
list1 = list(map(int,input().split()))  # str.split() 切割字符串返回list类型
  # map(f,list) 将函数f作用用list的每个元素，返回map类型，用list() 强制类型转换成list类型        

show(list1)

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

Submission status: Accepted

Solution code:
def insertion_sort(a):
    for i in range(1,len(a)):
        key = a[i]
        j = i-1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]
            j = j-1
        a[j+1] = key
        print(*a,sep=' ')
    return a


if __name__ == '__main__':
    n = input()
    a = list(map(int,input().split()))
    print(*a,sep=' ')
    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):
    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:
N = int(input())
A = list(map(int, input().split()))

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



insertionSort(A, N)

Submission status: Accepted

Solution code:
def list_print(A):
    ret = str(A[0])
    for i in range(1, len(A)):
        ret += " " + str(A[i])

    print(ret)
    return True


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

    list_print(A)

Submission status: Accepted

Solution code:
import sys


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


n = int(sys.stdin.readline())
a = [int(v) for v in sys.stdin.readline().strip().split()]
insertion_sort(a)

Submission status: Accepted

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

print(' '.join(map(str, sortlist)))
for i in range(1,n):
    temp = sortlist[i]
    if temp < sortlist[i-1]:
        j = i
        while True:
            sortlist[j] = sortlist[j-1]
            j -= 1
            if j ==0 or temp >= sortlist[j-1]:
                break
        sortlist[j] = temp
        print(' '.join(map(str, sortlist)))
    else:
        print(' '.join(map(str, sortlist)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(0, n-1):
    print(a[i], end=" ")
print(a[n-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 i in range(0, n-1):
        print(a[i], end=" ")
    print(a[n-1])