Sorting 

One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms. 

Insertion Sort 

These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with a nearly sorted list.

Insert element into sorted list 

Given a sorted list with an unsorted number $\boldsymbol{\mathrm{~e~}}$ in the rightmost cell, can you write some simple code to insert $\boldsymbol{\mathrm{~e~}}$ into the array so that it remains sorted?  

Since this is a learning exercise, it won't be the most efficient way of performing the insertion.  It will instead demonstrate the brute-force method in detail.   

Assume you are given the array $arr=[1,2,4,5,3]$ indexed $\boldsymbol{0}...4$.  Store the value of $ar r[4]$.  Now test lower index values successively from $3$ to $\mbox{0}$ until you reach a value that is lower than $ar r[4]$, at $ar r[1]$ in this case.  Each time your test fails, copy the value at the lower index to the current index and print your array.  When the next lower indexed value is smaller than $ar r[4]$, insert the stored value at the current index and print the entire array.

Example 

$n=5$ 

$arr=[1,2,4,5,3]$ 

Start at the rightmost index.  Store the value of $ar r[4]=3$.  Compare this to each element to the left until a smaller value is reached.  Here are the results as described:  

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

Function Description

Complete the insertionSort1 function in the editor below.  

insertionSort1 has the following parameter(s):

n: an integer, the size of $\textbf{arr}$  
arr: an array of integers to sort  

Returns  

None:  Print the interim and final arrays, each on a new line.  No return value is expected.  

Input Format

The first line contains the integer $n$, the size of the array $\textbf{arr}$. 

The next line contains $n$ space-separated integers $ar r[0]...ar r[n-1]$. 

Constraints

$1\leq n\leq1000$ 

$-10000\leq arr[i]\leq10000$  

Output Format

Print the array as a row of space-separated integers each time there is a shift or insertion.

Sample Input
5
2 4 6 8 3

Sample Output
2 4 6 8 8 
2 4 6 6 8 
2 4 4 6 8 
2 3 4 6 8 

Explanation

$3$ is removed from the end of the array.

In the $1^{st}$ line $8>3$, so $8$ is shifted one cell to the right. 

In the $2^{nd}$ line $6>3$, so $\boldsymbol{6}$ is shifted one cell to the right. 

In the $3^{rd}$ line $4>3$, so $\begin{array}{c}4\end{array}$ is shifted one cell to the right. 

In the $ 4^{th}$ line $2<3$, so $3$ is placed at position $\mbox{1}$.  

Next Challenge

In the next Challenge, we will complete the insertion sort.

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
n = int(input())
d = [int(x) for x in input().split()]
t = d[n - 1]
k = n - 2
while k >= 0 and t < d[k]:
	d[k + 1] = d[k]
	s = str(d)[1:-1].replace(',', '')
	print(s)
	k -= 1
d[k + 1] = t
s = str(d)[1:-1].replace(',', '')
print(s)


size = int(input())
array = input().split(' ')
arr = ['None'] * size
for i in range(size):
	arr[i] = int(array[i])
i = size - 1
while i > 0:
	tmp = arr[i]
	j = i - 1
	while arr[j] > tmp and j > -1:
		arr[j + 1] = arr[j]
		for k in range(size):
			print(arr[k], end=' ')
		print()
		j = j - 1
	arr[j + 1] = tmp
	i = i - 1
for k in range(size):
	print(arr[k], end=' ')


size = int(input())
if size == 1:
	print(int(input()))
elif True:
	array = []
	output = ''

	def toString(l):
		rv = ''
		for elem in l:
			rv += str(elem)
			rv += ' '
		return rv[:-1] + '\n'
	for elem in input().split():
		array.append(int(elem))
	toInsert = array[-1]
	currIndex = -1
	while toInsert <= array[currIndex - 1]:
		currIndex -= 1
		array[currIndex + 1] = array[currIndex]
		output += toString(array)
		if currIndex + size == 0:
			break
	array[currIndex] = toInsert
	output += toString(array)
	print(output[:-1])


size = int(input())
input_array = input().split()
array = [int(x) for x in input_array]
V = array[size - 1]
i = size - 2
while V < array[i] and i >= 0:
	array[i + 1] = array[i]
	i -= 1
	print(' '.join([str(x) for x in array]))
array[i + 1] = V
print(' '.join([str(x) for x in array]))


def insertionSort(x):
	p = len(x) - 1
	for k in range(p):
		y = x[-1]
		if y < x[-2]:
			for i in range(p, 0, -1):
				if x[i - 1] >= y:
					x[i] = x[i - 1]
					print(' '.join((str(j) for j in x)))
				else:
					x[i] = y
					break
			if x[0] >= x[1]:
				x[0] = y
		else:
			break
	print(' '.join((str(j) for j in x)))
	return x
m = input()
ar = [int(i) for i in input().strip().split()]
insertionSort(ar)


from collections import deque

def insertationSort(ar):
	left = deque(ar)
	right = deque()
	v = left.pop()
	while left and v < left[-1]:
		print(' '.join((str(x) for x in left)), end=' ')
		right.appendleft(left.pop())
		print(' '.join((str(x) for x in right)))
	left.append(v)
	left.extend(right)
	print(' '.join((str(x) for x in left)))
n = input()
ar = input().split()
insertationSort(ar)


s = int(input())
ar = [int(x) for x in input().split()]
x = ar[s - 1]
i = s - 2
while True:
	ar[i + 1] = ar[i]
	i = i - 1
	for n in ar:
		print(n, end=' ')
	print()
	if i == -1 or x >= ar[i]:
		break
ar[i + 1] = x
for x in ar:
	print(x, end=' ')


import sys
count = None
V = None
a_list = None
for line in sys.stdin:
	if count is None:
		count = int(line.strip())
		continue
	a_list = [int(i) for i in line.strip().split(' ')]
V = a_list[-1]
for i in range(count - 1):
	if V >= a_list[count - 2 - i]:
		a_list[count - 2 - i + 1] = V
		print(' '.join([str(j) for j in a_list]))
		break
	else:
		a_list[count - 2 - i + 1] = a_list[count - 2 - i]
		print(' '.join([str(j) for j in a_list]))
if V not in a_list:
	a_list[0] = V
	print(' '.join([str(j) for j in a_list]))


def insertionSort(ar):
	V = ar[-1]
	x = -1
	while x + len(ar) > 0 and ar[x - 1] > V:
		ar[x] = ar[x - 1]
		x -= 1
		print(' '.join(ar))
	ar[x] = V
	print(' '.join(ar))
if int(input()) > 1:
	ar = input().split(' ')
	insertionSort(ar)
else:
	print(input())


import sys

def insertionSort(ar):
	toInsert = ar.pop().strip()
	ar.append(ar[-1])
	output = ''
	i = len(ar) - 2
	done = False
	while i >= 0 and (not done):
		if ar[i] > toInsert:
			ar[i + 1] = ar[i]
		else:
			ar[i + 1] = toInsert
			done = True
		for val in ar:
			output += str(val) + ' '
		output += '\n'
		i -= 1
	if not done:
		ar[0] = toInsert
		for val in ar:
			output += str(val) + ' '
	return output.strip()
length = int(sys.stdin.readline())
array = sys.stdin.readline().split(' ')
print(insertionSort(array[0:length]))


def insertionSort(ar):
	u = ar[-1]
	for i in range(len(ar) - 2, -1, -1):
		if u < ar[i]:
			ar[i + 1] = ar[i]
			print(' '.join([str(i) for i in ar]))
		else:
			ar[i + 1] = u
			print(' '.join([str(i) for i in ar]))
			return
	ar[0] = u
	print(' '.join([str(i) for i in ar]))
	return
m = int(input())
ar = [int(i) for i in input().strip().split()]
if m == 1:
	print(' '.join([str(i) for i in ar]))
elif m == len(ar):
	insertionSort(ar)


def insertionSort(m, ar):
	if m == 1:
		print(ar[0])
	else:
		item = ar[-1]
		index = -2
		while index >= -m and item < ar[index]:
			ar[index + 1] = ar[index]
			for element in ar:
				print(element, end=' ')
			print()
			index -= 1
		ar[index + 1] = item
		for element in ar:
			print(element, end=' ')
		print()
m = int(input())
ar = [int(i) for i in input().strip().split()]
insertionSort(m, ar)


s = input()
ar = input()

def insertionSort(ar):
	ar = ar.split()
	s = len(ar) - 2
	check = int(ar[-1])
	for x in range(s, -1, -1):
		if int(ar[x]) <= check:
			ar[x + 1] = str(check)
			print(' '.join(ar))
			break
		else:
			ar[x + 1] = ar[x]
			print(' '.join(ar))
			if x == 0:
				ar[0] = str(check)
				print(' '.join(ar))
insertionSort(ar)


import sys

def display(array):
	[print(x, end=' ') for x in array]
	print()
N = int(sys.stdin.readline())
array = [int(X) for X in sys.stdin.readline().split()]
num = array[-1]
for i in range(N - 2, -1, -1):
	if array[i] > num and i != 0:
		array[i + 1] = array[i]
		display(array)
	elif array[i] > num and i == 0:
		array[i + 1] = array[i]
		display(array)
		array[i] = num
		display(array)
	else:
		array[i + 1] = num
		display(array)
		break


def printArray(ar):
	text = ''
	for elem in ar:
		text += str(elem) + ' '
	text = text[:len(text) - 1]
	print(text)

def insertionSort(ar):
	n = ar[len(ar) - 1]
	for i in range(len(ar) - 2, -1, -1):
		k = ar[i]
		if k > n:
			ar[i + 1] = k
			printArray(ar)
		elif k < n:
			ar[i + 1] = n
			printArray(ar)
			return
	ar[0] = n
	printArray(ar)
m = eval(input())
ar = [int(i) for i in input().strip().split()]
insertionSort(ar)


x = int(input())
a = input().split()
v = int(a[x - 1])
i = x - 2
found = 0
while i >= 0:
	t = int(a[i])
	if t > v:
		a[i + 1] = t
	else:
		a[i + 1] = v
		found = 1
	for num in a:
		print(num, end=' ')
	print()
	if found:
		break
	i -= 1
if not found:
	a[0] = v
	for num in a:
		print(num, end=' ')
	print()


__author__ = 'Ben'
S = input()
ar = input()
ar = ar.split()
S = ar.__len__() - 1
val = ar[S]
S -= 1
while ar[S] > val and S >= 0:
	ar[S + 1] = ar[S]
	S -= 1
	tmp = ar[S]
	print('%s' % ' '.join(map(str, ar)), '')
ar[S + 1] = val
print('%s' % ' '.join(map(str, ar)), '')


def insertionSort(ar):
	x = len(ar)
	v = ar[x - 1]
	j = x - 2
	while ar[j] > v:
		for i in range(0, j + 1):
			print(ar[i], end=' ')
		print(ar[j], end=' ')
		for i in range(j + 2, x):
			print(ar[i - 1], end=' ')
		j = j - 1
		print('')
	for k in range(0, j + 1):
		print(ar[k], end=' ')
	print(v, end=' ')
	for k in range(j + 2, x):
		print(ar[k - 1], end=' ')
	print('')
n = int(input(''))
elem = input('')
numbers = elem.split()
arr = []
for i in range(0, n):
	arr.append(int(numbers[i]))
insertionSort(arr)


r = int(input())
g_numbers = [int(v) for v in input().split(' ')]
g_num = g_numbers[-1]
for x in range(len(g_numbers) - 2, -1, -1):
	if g_numbers[x] >= g_num:
		g_numbers[x + 1] = g_numbers[x]
		print('%s' % ' '.join(map(str, g_numbers)))
		if x == 0:
			g_numbers[0] = g_num
			print('%s' % ' '.join(map(str, g_numbers)))
	else:
		g_numbers[x + 1] = g_num
		print('%s' % ' '.join(map(str, g_numbers)))
		break


def recursive_print(ar):
	if ar == []:
		return ''
	return str(ar[0]) + ' ' + recursive_print(ar[1:])

def insertionSort(ar):
	val = len(ar) - 1
	temp = ar[val]
	while ar[val - 1] > temp and val > 0:
		ar[val] = ar[val - 1]
		val -= 1
		print(recursive_print(ar))
	ar[val] = temp
	print(recursive_print(ar))
input()
ar = input().split()
insertionSort(ar)


def sort(li, i):
	j = i - 1
	while j >= 0:
		if li[j] <= li[i]:
			break
		help = li[i]
		li[i] = li[j]
		print(' '.join(map(str, li)))
		li[j] = help
		i -= 1
		j -= 1
	print(' '.join(map(str, li)))
n = int(input())
array = [int(x) for x in input().split()]
sort(array, n - 1)


def insertionSort(ar):
	key = ar[-1]
	index = len(ar) - 1
	while index > 0:
		if ar[index - 1] > key:
			ar[index] = ar[index - 1]
			index = index - 1
			print(*ar)
		else:
			ar[index] = key
			print(*ar)
			break
	if index == 0:
		ar[0] = key
		print(*ar)
num = [int(i) for i in input().strip().split()]
ar = [int(j) for j in input().strip().split()]
insertionSort(ar)


import sys

def print_ar(a):
	for i in a:
		print(i, end=' ')
	print('')
n = int(sys.stdin.readline())
raw = sys.stdin.readline().split()
ar = []
for i in raw:
	ar.append(int(i))
key = ar[n - 1]
k = n - 1
for i in range(n - 2, -1, -1):
	if key < ar[i]:
		ar[i + 1] = ar[i]
		print_ar(ar)
		k = k - 1
	else:
		break
ar[k] = key
print_ar(ar)


def insertionSort(arr):
	length = len(arr)
	v = arr[length - 1]
	for i in range(length - 2, -1, -1):
		if arr[i] > v:
			arr[i + 1] = arr[i]
			s = ''
			for j in arr:
				s += repr(j) + ' '
			print(s.strip())
		else:
			arr[i + 1] = v
			s = ''
			for j in arr:
				s += repr(j) + ' '
			print(s.strip())
			break
	if arr[0] > v:
		arr[0] = v
		s = ''
		for j in arr:
			s += repr(j) + ' '
		print(s.strip())
length = int(input())
arr = []
temp = input().strip().split()
for i in range(0, len(temp)):
	arr.append(int(temp[i]))
insertionSort(arr)


import sys

def insertionSort(ar):
	e = int(len(ar)) - 1
	newNum = ar[e]
	done = False
	while done == False:
		if ar[e - 1] > newNum:
			ar[e] = ar[e - 1]
			e -= 1
			done = e == 0
			buildString(ar)
		else:
			done = True
	ar[e] = newNum
	return buildString(ar)

def buildString(ar):
	string = str(' ')
	for i in range(len(ar)):
		string += str(ar[i]) + ' '
	sys.stdout.write(string.strip() + '\n')
	return string

def raw_input():
	m = input()
	return m

def main():
	m = int(input())
	i = int(0)
	ar = list()
	ar = [int(i) for i in raw_input().strip().split()]
	insertionSort(ar)
	sys.exit(0)
main()


arrSize = int(input())
strArr = str(input()).split(' ')
intArr = [int(i) for i in strArr]
if arrSize == 1:
	print(' '.join([str(i) for i in intArr]))
key = intArr[arrSize - 1]
index = arrSize - 2
cont = True
while cont:
	if index < 0:
		intArr[index + 1] = key
		cont = False
	elif intArr[index] > key:
		intArr[index + 1] = intArr[index]
		index -= 1
	elif intArr[index] <= key:
		intArr[index + 1] = key
		cont = False
	print(' '.join([str(i) for i in intArr]))


length = int(input())
array = [int(i) for i in input().split()]
index = length - 1
value = array[index]
while index > 0 and value < array[index - 1]:
	array[index] = array[index - 1]
	print(*array)
	index -= 1
array[index] = value
print(*array)


import sys

def sort(stdin):
	size = int(stdin.readline())
	array = [int(i) for i in stdin.readline().split()]
	idx = size - 1
	shiftOff = array[idx]
	shifter(array, shiftOff, idx)

def shifter(array, shiftedOff, idx):
	if array[idx - 1] > shiftedOff and idx > 0:
		array[idx] = array[idx - 1]
		print(*array)
		shifter(array, shiftedOff, idx - 1)
	else:
		array[idx] = shiftedOff
		print(*array)
sort(sys.stdin)


import sys

def print_list(ar):
	print(' '.join(map(str, ar)))

def insertion_sort(ar):
	if len(ar) == 1:
		print_list(ar)
		return ar
	else:
		x = ar[-1]
		for i in reversed(range(len(ar) - 1)):
			if x < ar[i]:
				ar[i + 1] = ar[i]
				print_list(ar)
				if i == 0:
					ar[0] = x
					print_list(ar)
					break
			else:
				ar[i + 1] = x
				print_list(ar)
				break
		return ar
s = int(sys.stdin.readline())
ar = list(map(int, sys.stdin.readline().split()))
insertion_sort(ar)


size = input()
size = int(size)
text = input()
array = [int(n) for n in text.split()]
oddManOut = array[len(array) - 1]
for a in range(size + 1):
	if not a == 0:
		num = array[size - a - 1]
		if oddManOut < num and (not a == size):
			array[size - a] = num
			printOut = ''
			for c in array:
				printOut = printOut + str(c) + ' '
			print(str(printOut))
		else:
			extraMod = size + 99
			if oddManOut < num:
				extraMod = 1
			array[(size - a) % extraMod] = oddManOut
			printOut = ''
			for c in array:
				printOut = printOut + str(c) + ' '
			print(printOut)
			break


import sys
t = int(input())
a = sys.stdin.readline().split()
idx = t - 1
while True:
	for x in range(0, t):
		if x == idx and idx == 0:
			sys.stdout.write('{} '.format(a[idx]))
		elif x == idx and a[idx - 1] > a[idx]:
			sys.stdout.write('{} '.format(a[idx - 1]))
			(a[idx], a[idx - 1]) = (a[idx - 1], a[idx])
		elif x == idx and a[idx - 1] <= a[idx]:
			sys.stdout.write('{} '.format(a[x]))
			idx = -1
		else:
			sys.stdout.write('{} '.format(a[x]))
	idx = idx - 1
	sys.stdout.write('\n')
	if a[idx + 1] == a[idx] or idx < 0:
		break


import sys
s = int(input())
number = input()
l = [int(s) for s in number.split()]
V = l[s - 1]
next = s - 2
while V < l[next]:
	l[next + 1] = l[next]
	for i in range(0, s):
		print(l[i], end=' ')
	next = next - 1
	print()
	if next < 0:
		break
l[next + 1] = V
for i in range(0, s):
	print(l[i], end=' ')


s = input()
l = input().split()
e = l[-1]
for i in range(len(l) - 2, -1, -1):
	if l[i] < e:
		break
	l[i + 1] = l[i]
	print(' '.join(l))
l[i + 1 if l[i] < e else i] = e
print(' '.join(l))


import sys

def print_out(ar):
	print(' '.join([str(x) for x in ar]))

def insertionSort(ar):
	if not ar:
		return
	insert_val = ar[-1]
	for check_val in reversed(ar[:-1]):
		if check_val > insert_val:
			ar[ar.index(check_val) + 1] = check_val
		else:
			ar[ar.index(check_val) + 1] = insert_val
			break
		print_out(ar)
	if insert_val < ar[0]:
		ar[0] = insert_val
	print_out(ar)
stuff = sys.stdin.readlines()
if not stuff:
	exit(0)
size = int(stuff[0])
if not size:
	exit(0)
ar = [int(x) for x in stuff[1].split(' ')]
insertionSort(ar)


def display(ar):
	for i in ar:
		print(i, end=' ')
	print()

def insertionSort(ar):
	v = ar[len(ar) - 1]
	index = len(ar) - 1
	while ar[index - 1] > v:
		ar[index] = ar[index - 1]
		index -= 1
		display(ar)
		if index == 0:
			break
	ar[index] = v
	display(ar)
n = int(input())
l = []
temp = input().split(' ')
count = 0
for i in temp:
	count += 1
	l.append(int(i))
	if count == n:
		break
insertionSort(l)


n = int(input())
ar = [int(x) for x in input().split(' ')]
i = ar[-1]
n -= 2
while n >= 0 and i < ar[n]:
	ar[n + 1] = ar[n]
	print(' '.join([str(x) for x in ar]))
	n -= 1
ar[n + 1] = i
print(' '.join([str(x) for x in ar]))


import copy

def printArrayAsString(arToPrint):
	strInt = []
	for val in arToPrint:
		strInt.append(str(val))
	print(' '.join(strInt))

def basicInsertionSort(arIntegers):
	arIntProcess = copy.copy(arIntegers)
	intToSort = arIntegers[len(arIntegers) - 1]
	for val in reversed(range(len(arIntProcess))):
		arIntProcess[val] = arIntegers[val - 1] if arIntegers[val - 1] > intToSort else intToSort
		printArrayAsString(arIntProcess)
		if arIntegers[val - 1] < intToSort:
			break
	return arIntProcess

def main():
	strNumLengthArray = input()
	stringIntRepresentation = input()
	arStringInt = stringIntRepresentation.split()
	numLengthArray = int(strNumLengthArray)
	arInt = []
	for str in arStringInt:
		arInt.append(int(str))
	if len(arInt) == numLengthArray:
		basicInsertionSort(arInt)
	else:
		print('Not valid input')
main()


def start():
	s = int(input())
	text = input().split(' ')
	a = list()
	for item in text:
		a.append(int(item))
	sort(a)

def printArray(array):
	n = len(array) - 1
	for i in range(n):
		print(array[i], ' ', sep='', end='')
	print(array[n])

def sort(array):
	n = len(array) - 1
	num = array[n]
	for i in range(n, -1, -1):
		if array[i - 1] > num and i > 0:
			array[i] = array[i - 1]
			printArray(array)
		else:
			array[i] = num
			printArray(array)
			break
start()


def printArr(arr):
	for i in range(len(arr)):
		print(arr[i], end=' ')
size = int(input())
arr = input().strip().split()
arr = [int(entry) for entry in arr]
key = arr[-1]
j = size - 2
while j >= 0 and arr[j] > key:
	arr[j + 1] = arr[j]
	j -= 1
	printArr(arr)
	print()
arr[j + 1] = key
printArr(arr)


def insert(n, array, v):
	for i in [n - i - 1 for i in range(n)]:
		if i - 1 >= 0:
			if array[i - 1] > v:
				array[i] = array[i - 1]
				print(' '.join((str(x) for x in array)))
			else:
				array[i] = v
				print(' '.join((str(x) for x in array)))
				break
		else:
			array[i] = v
			print(' '.join((str(x) for x in array)))
			break
n = int(input())
a = input()
array = [int(x) for x in a.split()]
insert(n, array, array[n - 1])


l = []
n = int(input())
l = input().split(' ')
for i in range(0, n):
	l[i] = int(l[i])
x = l[n - 1]
i = n - 2
while (i >= 0) & (x < l[i]):
	l[i + 1] = l[i]
	i = i - 1
	for j in range(0, n):
		print('%d ' % l[j], end='')
	print()
l[i + 1] = x
for j in range(0, n):
	print('%d ' % l[j], end='')
print()


n = int(input())
nums = list(map(int, input().split()))
val = nums[-1]
i = len(nums) - 1
while i > 0 and nums[i - 1] > val:
	nums[i] = nums[i - 1]
	print(' '.join(map(str, nums)))
	i = i - 1
nums[i] = val
print(' '.join(map(str, nums)))


import fileinput

def arrayPrint(loi):
	retString = ''
	itr = 0
	while itr < len(loi):
		if itr == 0:
			retString += str(loi[itr])
		else:
			retString = retString + ' ' + str(loi[itr])
		itr = itr + 1
	return retString

def insertionSort(numInts, loi):
	lastIndex = numInts - 1
	currIndex = lastIndex - 1
	temp = loi[lastIndex]
	flag = False
	while currIndex >= 0:
		if loi[currIndex] > temp:
			loi[lastIndex] = loi[currIndex]
			currIndex = currIndex - 1
			lastIndex = lastIndex - 1
		else:
			loi[lastIndex] = temp
			flag = True
			break
		print(arrayPrint(loi))
	if not flag:
		loi[0] = temp
	print(arrayPrint(loi))
itr = 0
numInts = 0
loi = []
for line in fileinput.input():
	if itr == 0:
		numInts = int(line)
		itr = itr + 1
	else:
		loi = line.split(' ')
itr = 0
for i in loi:
	loi[itr] = int(i)
	itr = itr + 1
insertionSort(numInts, loi)


def insertionSort(a):
	v = a[-1]
	i = len(a) - 2
	while v <= a[i] and i >= 0:
		a[i + 1] = a[i]
		for ele in a:
			print(ele, end=' ')
		print('')
		i -= 1
	a[i + 1] = v
	for ele in a:
		print(ele, end=' ')
n = int(input())
a = list(map(int, input().split()))
insertionSort(a)


import sys

def print_num(num):
	for i in range(len(num) - 1):
		sys.stdout.write(str(num[i]))
		sys.stdout.write(' ')
	print(num[-1])
n = int(input())
num = input().split()
num = [int(i) for i in num]
newKey = num[-1]
for i in reversed(range(n - 1)):
	if newKey < num[i]:
		num[i + 1] = num[i]
		print_num(num)
	else:
		num[i + 1] = newKey
		print_num(num)
		break
if newKey < num[0]:
	num[0] = newKey
	print_num(num)


N = int(input())
arr = input().split()
for i in range(N):
	arr[i] = int(arr[i], 10)
v = arr[N - 1]
srt = False
l = N
N = N - 1
while not srt:
	if N == 0 or v > arr[N - 1]:
		arr[N] = v
		srt = True
	else:
		arr[N] = arr[N - 1]
	for j in range(l):
		print(arr[j], end=' ')
	print()
	N = N - 1


input('')
ar = input('').split()
V = ar[-1]
l = len(ar)
for i in range(1, l):
	if V < ar[l - i - 1]:
		ar[l - i] = ar[l - i - 1]
	else:
		ar[l - i] = V
		break
	print(' '.join(ar))
else:
	ar[0] = V
print(' '.join(ar))


s = int(input())
p = s
tmp = input()
ar = tmp.split(' ')
ar = [int(i) for i in ar]
var = ar[s - 1]
flag = False
while not flag:
	if s == 1:
		ar[s - 1] = var
		flag = True
	elif ar[s - 2] > var:
		ar[s - 1] = ar[s - 2]
		s = s - 1
	else:
		ar[s - 1] = var
		flag = True
	ans = ''
	for i in range(p):
		ans = ans + str(ar[i]) + ' '
	print(ans)


num = input()
array = input()
num = int(num)
array = array.split(' ')
V = int(array[len(array) - 1])
for i in range(len(array) - 1, -1, -1):
	if V < int(array[i - 1]) and (not i == 0):
		array[i] = array[i - 1]
		print(*array)
	else:
		array[i] = str(V)
		print(*array)
		break


def print_arr(l):
	print(' '.join((str(x) for x in l)))

def insert(l):
	x = l[-1]
	i = len(l) - 1
	while True:
		i -= 1
		if i == -1:
			l[0] = x
			print_arr(l)
			return
		if l[i] > x:
			l[i + 1] = l[i]
			print_arr(l)
		elif l[i] <= x:
			l[i + 1] = x
			print_arr(l)
			return

def main():
	length = int(input())
	l = list((int(x) for x in input().split(' ')))
	insert(l)
main()


x = int(input())
ar = []
l = input().split()
for i in l:
	ar.append(int(i))
ins = 0
temp = ar[-1]
for i in range(len(ar) - 2, -1, -1):
	if ar[i] >= temp:
		ar[i + 1] = ar[i]
		print(' '.join((str(i) for i in ar)))
	else:
		ins = 1
		break
if ins == 0:
	ar[0] = temp
else:
	ar[i + 1] = temp
print(' '.join((str(i) for i in ar)))


s = int(input())
ar = input().split(' ')
test = False
v = ar[s - 1]
for i in range(s - 2, -1, -1):
	if ar[i] > v:
		ar[i + 1] = ar[i]
		print(' '.join(ar))
		if i == 0:
			ar[0] = v
			break
	else:
		ar[i + 1] = v
		break
print(' '.join(ar))


s = int(input())
ar = input().split(' ')
number = ar[-1]
i = -1
while i + s > 0 and ar[i - 1] > number:
	ar[i] = ar[i - 1]
	print(' '.join(ar))
	i = i - 1
ar[i] = number
print(' '.join(ar))


s = int(input())
numbers = input().split(' ')
V = numbers[s - 1]
i = s - 1
checker = True
while i >= 0 and checker == True:
	if i == 0:
		numbers[i] = V
		print(' '.join(numbers))
		i = i - 1
		checker = False
	elif V < numbers[i - 1]:
		numbers[i] = numbers[i - 1]
		print(' '.join(numbers))
		i = i - 1
	elif V >= numbers[i - 1]:
		numbers[i] = V
		print(' '.join(numbers))
		i = i - 1
		checker = False


input()
ar = input().split(' ')
v = int(ar[-1])
ar = list(map(lambda x: int(x), ar))
length = len(ar)
i = 1
run = True
while run:
	if i == length:
		ar[0] = v
		run = False
	elif v < ar[-(i + 1)]:
		ar[-i] = ar[-(i + 1)]
		i = i + 1
		print(' '.join(map(lambda x: str(x), ar)))
	else:
		run = False
		ar[-i] = v
print(' '.join(map(lambda x: str(x), ar)))


s = int(input())
ar = input().split(' ')
e = ar[-1]

def print_array(ar):
	str = ''
	for i in ar:
		str += i + ' '
	print(str.strip())
isinserted = False
for i in range(s - 2, -1, -1):
	if e < ar[i]:
		ar[i + 1] = ar[i]
		print_array(ar)
	else:
		isinserted = True
		ar[i + 1] = e
		print_array(ar)
		break
if not isinserted:
	ar[0] = e
	print_array(ar)


s = int(input())
ar = [int(word) for word in input().split(' ')]

def insertionSort(ar):
	target = ar[-1]
	index = len(ar) - 2
	for i in range(len(ar) - 2, -1, -1):
		if ar[i] > target:
			ar[i + 1] = ar[i]
			print(' '.join(map(str, ar)))
		else:
			ar[index + 1] = target
			break
		index -= 1
	if index == -1:
		ar[index + 1] = target
	print(' '.join(map(str, ar)))
insertionSort(ar)


def printArray(array):
	for i in range(0, len(array)):
		print(array[i], end=' ')
s = int(input()) - 1
ar = input()
ar = ar.split()
v = int(ar[s])
for x in range(1, s + 1):
	if v < int(ar[s - x]):
		ar[s - x + 1] = ar[s - x]
		printArray(ar)
		print()
		if not s - x:
			ar[0] = v
			printArray(ar)
			break
	else:
		ar[s - x + 1] = v
		printArray(ar)
		break


import sys
lines = sys.stdin.readlines()
nums = lines[1].split(' ')
nums = [int(n) for n in nums if n]
v = nums[-1]
size = len(nums)
for i in range(size - 1, 0, -1):
	if nums[i - 1] > v:
		nums[i] = nums[i - 1]
		print(' '.join(map(str, nums)))
	else:
		nums[i] = v
		print(' '.join(map(str, nums)))
		break
else:
	nums[0] = v
	print(' '.join(map(str, nums)))


def insert(A):
	valueToInsert = A[-1]
	holePos = len(A) - 1
	while holePos > 0 and valueToInsert < A[holePos - 1]:
		A[holePos] = A[holePos - 1]
		holePos -= 1
		print(' '.join([str(k) for k in A]))
	A[holePos] = valueToInsert
	print(' '.join([str(k) for k in A]))
s = input()
array = [int(i) for i in input().split()]
insert(array)


x = input()
x = input()
x = x.split()
for i in range(len(x)):
	x[i] = int(x[i])
length = len(x)
var = None

def printlist(lis):
	string = ''
	for z in x:
		string += str(z) + ' '
	print(string[:-1])
for i in range(length - 1, 0, -1):
	if var == None:
		if x[i] < x[i - 1]:
			var = x[i]
			x[i] = x[i - 1]
			printlist(x)
		else:
			printlist(x)
			break
	else:
		if var >= x[i - 1]:
			x[i] = var
			printlist(x)
			break
		if var < x[i]:
			x[i] = x[i - 1]
			printlist(x)
else:
	x[0] = var
	printlist(x)


import sys
inp = sys.stdin.readlines()
array = [int(x) for x in inp[1].split()]
x = len(array) - 1
val = array[x]
while x > 0 and val < array[x - 1]:
	array[x] = array[x - 1]
	print(' '.join((str(x) for x in array)))
	x -= 1
array[x] = val
print(' '.join((str(x) for x in array)))


def insertion_sort(a):
	v = a[-1]
	for i in range(len(a) - 2, -1, -1):
		if a[i] > v:
			a[i + 1] = a[i]
			yield
		else:
			a[i + 1] = v
			return
	else:
		a[0] = v
		return
size = input()
line = input()
line = line.split(' ')
for iteration in insertion_sort(line):
	print(' '.join(line))
else:
	print(' '.join(line))


def strl(l):
	s = ''
	for i in l:
		s += str(i) + ' '
	return s[:-1]
n = int(input())
(a, *l) = map(int, ['1'] + input().split())
del a
V = l[-1]
for i in range(n - 2, -1, -1):
	if l[i] > V:
		l[i + 1] = l[i]
		print(strl(l))
		if i == 0:
			l[0] = V
			print(strl(l))
			break
	else:
		l[i + 1] = V
		print(strl(l))
		break


import sys

def in_loc(a, n):
	V = a[n - 1]
	for i in range(n - 2, -1, -1):
		if a[i] > V:
			a[i + 1] = a[i]
		else:
			a[i + 1] = V
			break
		print(*a, sep=' ')
	if a[0] == a[1]:
		a[0] = V
	print(*a, sep=' ')

def main():
	n = int(input())
	a = input()
	b = a.split()
	a = [int(x) for x in b]
	in_loc(a, n)
main()


size = int(input())
v = [int(i) for i in input().strip().split()]
a = v[-1]
n = size - 2
while n >= 0 and v[n] > a:
	v[n + 1] = v[n]
	print(*v, sep=' ')
	n -= 1
if n == -1:
	v[0] = a
else:
	v[n + 1] = a
print(*v, sep=' ')


s = int(input())
ar = input().split()
v = ar[-1]
if s == 1:
	print(ar[0])
else:
	for i in range(1, s + 1):
		if i == s:
			ar[-i] = v
			print(' '.join(ar))
		elif int(ar[-i - 1]) > int(v):
			ar[-i] = ar[-i - 1]
			print(' '.join(ar))
		else:
			ar[-i] = v
			print(' '.join(ar))
			break


input()
nums = list(map(int, input().split()))
ins = nums[-1]
index = len(nums) - 2
while nums[index] > ins and index >= 0:
	nums[index + 1] = nums[index]
	print(' '.join(map(str, nums)))
	index -= 1
nums[index + 1] = ins
print(' '.join(map(str, nums)))


import fileinput
lines = fileinput.input()
currentindex = int(lines[0]) - 1
ar = [int(x) for x in lines[1].rstrip().split(' ')]
done = False
v = ar[-1]
while not done:
	if currentindex == 0 or (v <= ar[currentindex] and v > ar[currentindex - 1]):
		ar[currentindex] = v
		done = True
	else:
		ar[currentindex] = ar[currentindex - 1]
		currentindex -= 1
	print(format(' '.join(map(str, ar))))


import sys
x = int(input())
arr = input()
arr = list(map(int, arr.split()))
newV = arr[-1]
if newV == arr[-2]:
	sys.exit()
for i in range(x - 2, -1, -1):
	val = arr[i]
	if newV < val:
		arr[i + 1] = val
		print(' '.join((str(p) for p in arr)))
		if i == 0:
			arr[i] = newV
			print(' '.join((str(p) for p in arr)))
	else:
		arr[i + 1] = newV
		print(' '.join((str(p) for p in arr)))
		break


def insertion():
	size = int(input())
	inp_str = str(input().strip())
	inp_list = [int(x) for x in inp_str.split(' ')]
	a = inp_list[-1]
	for j in range(1, len(inp_list)):
		element_v = inp_list[j]
		pre_element = j - 1
		while pre_element >= 0 and element_v < inp_list[pre_element]:
			inp_list[pre_element + 1] = inp_list[pre_element]
			print(' '.join((str(x) for x in inp_list)))
			pre_element = pre_element - 1
	inp_list[pre_element + 1] = a
	print(' '.join((str(x) for x in inp_list)))

def main():
	insertion()
main()


length = input()
array = input()
a = array.split(' ')
tmp = int(a[len(a) - 1])
length = int(length)
length = length - 2
out = ''
while length > -1:
	out = ''
	if int(a[length]) > tmp:
		a[length + 1] = a[length]
		length = length - 1
		for i in range(len(a)):
			out = out + a[i] + ' '
		print(out[:-1])
	else:
		a[length + 1] = str(tmp)
		for i in range(len(a)):
			out = out + a[i] + ' '
		print(out[:-1])
		break
if a[0] == a[1]:
	out = ''
	a[0] = str(tmp)
	for i in range(len(a)):
		out = out + a[i] + ' '
	print(out[:-1])


n = int(input())
a = list(map(int, input().split()))
l = len(a)
e = a[-1]

def output(a):
	print(' '.join(list(map(str, a))))
i = l - 2
while True:
	if a[i] > e:
		a[i + 1] = a[i]
		output(a)
	else:
		a[i + 1] = e
		output(a)
		break
	if i == 0:
		if a[i] > e:
			a[i] = e
			output(a)
		break
	i -= 1


size = int(input())
array = list(map(int, input().split()))
V = array[size - 1]

def print_array(array):
	for elem in array:
		print(elem, end=' ')
	print('')
for _ in range(size):
	for i in range(size - 1):
		if array[i] > array[i + 1]:
			array[i + 1] = array[i]
			print_array(array)
			array[i] = V
			break
print_array(array)


def main():
	s = int(input())
	unsorted = list(map(int, input().rstrip().split()))
	item = unsorted[-1]
	marker = len(unsorted) - 2
	while item < unsorted[marker] and marker >= 0:
		unsorted[marker + 1] = unsorted[marker]
		strUnsorted = list(map(str, unsorted))
		print(' '.join(strUnsorted))
		marker -= 1
	unsorted[marker + 1] = item
	strUnsorted = list(map(str, unsorted))
	print(' '.join(strUnsorted))
	return 0
main()


def print_vec(vec):
	print(' '.join(map(str, vec)))
nn = int(input())
vec = list(map(int, input().split()))
for i in range(0, len(vec)):
	value = vec[i]
	j = i - 1
	while j >= 0 and vec[j] > value:
		vec[j + 1] = vec[j]
		print_vec(vec)
		j -= 1
	if j + 1 != i:
		vec[j + 1] = value
		print_vec(vec)


def print_arr(arr):
	print(' '.join(map(str, arr)))
size = input().strip()
size = list(map(int, size.split(' ')))
size = size[0]
arr = input().strip()
arr = list(map(int, arr.split(' ')))
i = size - 1
unsorted = arr[i]
while True:
	if i == 0:
		arr[0] = unsorted
		print_arr(arr)
		break
	item = arr[i] = arr[i - 1]
	if item < unsorted:
		arr[i] = unsorted
		print_arr(arr)
		break
	print_arr(arr)
	i -= 1


import fileinput

def insertionSort(ar):
	l = len(ar)
	inserted_element = ar[l - 1]
	index = l - 2
	while inserted_element < ar[index] and index >= 0:
		ar[index + 1] = ar[index]
		print_ar(ar)
		index -= 1
	ar[index + 1] = inserted_element
	print_ar(ar)

def print_ar(ar):
	for i in ar:
		print(str(i), end=' ')
	print()

def get_input():
	count = 1
	for line in fileinput.input():
		if count == 2:
			line = line.rstrip()
			ar = line.split(' ')
		count += 1
	insertionSort(ar)
get_input()


def insertion_sort(nums):
	for i in range(len(nums)):
		j = i - 1
		tmp = nums[i]
		while j != -1 and tmp < nums[j]:
			nums[j + 1] = nums[j]
			j -= 1
			print(' '.join(map(str, nums)))
		if j != i - 1:
			nums[j + 1] = tmp
			print(' '.join(map(str, nums)))
s = int(input())
ar = list(map(int, input().split()))
insertion_sort(ar)


def p(ar):
	print(' '.join(map(str, ar)))

def main():
	input()
	ar = [int(i) for i in input().split()]
	v = ar[len(ar) - 1]
	if len(ar) == 1:
		p(ar)
		return
	for i in reversed(range(len(ar) - 1)):
		if ar[i] > v:
			ar[i + 1] = ar[i]
			p(ar)
			if i == 0:
				ar[i] = v
				p(ar)
		else:
			ar[i + 1] = v
			p(ar)
			break
main()


def insertionSort(ar):
	sorted_list = ar
	to_insert = sorted_list[-1]
	i = len(sorted_list) - 2
	comparing = sorted_list[i]
	while to_insert < comparing and i >= 0:
		sorted_list[i + 1] = sorted_list[i]
		i -= 1
		print_list_as_string(sorted_list)
		comparing = sorted_list[i]
	sorted_list[i + 1] = to_insert
	print_list_as_string(sorted_list)

def print_list_as_string(l):
	stri = ''
	for j in l:
		stri += str(j) + ' '
	stri += ''
	print(stri)
m = input()
ar = [int(i) for i in input().strip().split()]
insertionSort(ar)


n = int(input(''))
ar = input('')
ar = ar.split(' ')
narray = []
last = ar[n - 1]
for i in range(1, n + 1):
	indice = n - (i + 1)
	if indice >= 0:
		previous = ar[n - (i + 1)]
		if previous > last:
			ar[n - i] = previous
			narray = ' '.join((str(e) for e in ar))
			print(narray)
		else:
			ar[n - i] = last
			narray = ' '.join((str(e) for e in ar))
			print(narray)
			break
	else:
		ar[0] = last
		narray = ' '.join((str(e) for e in ar))
		print(narray)
		break


def insort(L, e):
	L.append(e)
	i = len(L) - 1
	while i > 0 and L[i - 1] > e:
		L[i] = L[i - 1]
		i -= 1
		o = map(str, L)
		print(' '.join(o))
	L[i] = e
	o = map(str, L)
	print(' '.join(o))
size = int(input().strip().split()[0])
lst = [int(j) for j in input().strip().split()]
insort(lst[:-1], lst[-1])


n = int(input())
ar = [int(num) for num in input().split()]
a = ar[n - 1]
for i in range(n - 2, -1, -1):
	if ar[i] > a:
		ar[i + 1] = ar[i]
		for j in ar:
			print(j, end=' ')
	else:
		ar[i + 1] = a
		for j in ar:
			print(j, end=' ')
		break
	print()
else:
	ar[0] = a
	for j in ar:
		print(j, end=' ')


import sys
var = sys.stdin.readline()
line = sys.stdin.readline()
varArray = line.split()
x = varArray[int(var) - 1]
indexCount = 0
varArray
y = varArray[:int(var) - 1]
y.reverse()
flag = 1
for val in y:
	if val > x:
		varArray[-(indexCount + 1)] = val
		print(' '.join(varArray))
	else:
		varArray[-(indexCount + 1)] = x
		print(' '.join(varArray))
		flag = 0
		break
	indexCount += 1
if flag:
	varArray[0] = x
	print(' '.join(varArray))


def insertionSort(X):
	for i in range(1, len(X)):
		V = X[i]
		for j in range(i - 1, -1, -1):
			if X[j] > V:
				X[j + 1] = X[j]
				print(' '.join([str(e) for e in X]))
			else:
				X[j + 1] = V
				break
		if not j and i > 1 and (X[j + 1] != V):
			X[0] = V
	print(' '.join([str(e) for e in X]))

def main():
	input()
	insertionSort([int(e) for e in input().split(' ')])
main()


def insert(array, x):
	array += [x]
	i = len(array) - 2
	while x < array[i] and i >= 0:
		array[i + 1] = array[i]
		print(' '.join(('{}'.format(a) for a in array)))
		i -= 1
	array[i + 1] = x
	print(' '.join(('{}'.format(a) for a in array)))

def main():
	array_size = int(input())
	array = list(map(int, input().split()))
	insert(array[:-1], array[-1])
main()


n = int(input())
ar = input().split()
for i in range(0, n):
	temp = ar[n - (1 + i)]
	ar[n - (1 + i)] = ar[n - (2 + i)]
	print(' '.join(ar))
	ar[n - (2 + i)] = temp
	if (ar[n - (3 + i)] <= temp or n - (3 + i) == -1) and ar[n - (1 + i)] > temp:
		break
print(' '.join(ar))


import math
size = input()
arr = [int(x) for x in input().split()]
i = 1
while i + 1 <= len(arr) and arr[-i] < arr[-(i + 1)]:
	tmp = arr[-i]
	arr[-i] = arr[-(i + 1)]
	print(' '.join(map(str, arr)))
	arr[-(i + 1)] = tmp
	i += 1
print(' '.join(map(str, arr)))


def printarray(arr):
	print(' '.join(arr))

def insertionsort(aList, result):
	i = len(aList) - 1
	tmp = aList[i]
	k = i
	while k > 0 and tmp < aList[k - 1]:
		aList[k] = aList[k - 1]
		k -= 1
		flag = 1
		printarray(aList)
	aList[k] = tmp
	if flag == 1:
		printarray(aList)
input()
x = input().split()
insertionsort(x, 0)


def show_insertion_sort(L):
	for i in range(len(L)):
		_go = False
		val = L[i]
		j = i
		while j > 0 and L[j - 1] > val:
			_go = True
			L[j] = L[j - 1]
			j -= 1
			print(' '.join((str(e) for e in L)))
		if _go:
			L[j] = val
			print(' '.join((str(e) for e in L)))
n = int(input())
L = [int(s) for s in input().split()]
show_insertion_sort(L)


def insertion_sort(array):
	for index in range(1, len(array)):
		val = array[index]
		i = index - 1
		while i >= 0:
			if val < array[i]:
				array[i + 1] = array[i]
				print(' '.join(map(str, array)))
				array[i] = val
				i -= 1
			else:
				break
	print(' '.join(map(str, array)))
n = int(input())
vals = [int(i) for i in input().split()]
insertion_sort(vals)


def pprint(arr):
	row = ''
	for p in arr:
		row = row + str(p) + ' '
	print(row)

def swap(buf, index, arr):
	if buf > arr[index - 1] or index == 0:
		arr[index] = buf
		pprint(arr)
	else:
		arr[index] = arr[index - 1]
		pprint(arr)
		swap(buf, index - 1, arr)
length = int(input())
arr = [int(x) for x in input().split()]
swap(arr[length - 1], length - 1, arr)


def show():
	print(' '.join((str(x) for x in ar)))

def shift(i):
	ar[i + 1] = ar[i]
input()
ar = list(map(int, input().split()))
if len(ar) == 1 or ar[-2] <= ar[-1]:
	show()
	exit(0)
v = ar[-1]
for i in range(len(ar) - 2, -1, -1):
	shift(i)
	show()
	if ar[i - 1] < v < ar[i + 1]:
		ar[i] = v
		v = True
		break
if v is not True:
	shift(0)
	ar[0] = v
show()


s = input()
ar = input().split(' ')

def print_ar(ar):
	print(' '.join(ar))
s = int(s) - 1
value = ar[s]
s -= 1
for i in range(s, -1, -1):
	target = ar[i]
	if target > value:
		ar[i + 1] = target
		print_ar(ar)
	else:
		ar[i + 1] = value
		break
	if i == 0:
		ar[i] = value
print_ar(ar)


import sys

def print_list(data):
	for element in data:
		print(element, end=' ')
	print()
length = int(sys.stdin.readline())
data = []
raw = sys.stdin.readline().split()
for index in range(length):
	data.append(int(raw[index]))
element = data[-1]
try:
	for index in range(1, length):
		if data[-index - 1] <= element:
			raise StopIteration('Place found!')
		data[-index] = data[-index - 1]
		print_list(data)
	data[0] = element
except StopIteration:
	data[-index] = element
print_list(data)


s = int(input())
ar = list(map(int, input().split()))
v = ar[-1]
for j in range(s - 1, 0, -1):
	if v >= ar[j - 1]:
		ar[j] = v
		break
	ar[j] = ar[j - 1]
	print(' '.join(map(str, ar)))
else:
	ar[0] = v
print(' '.join(map(str, ar)))


def insertionSort(ar):
	i = len(ar) - 1
	V = ar[i]
	while i > 0 and ar[i - 1] > V:
		ar[i] = ar[i - 1]
		print(' '.join([str(v) for v in ar]))
		i -= 1
	ar[i] = V
	print(' '.join([str(v) for v in ar]))
s = int(input())
ar = [int(v) for v in input().split()]
insertionSort(ar)


n = int(input())
array = [int(val) for val in input().split()]
item = array[-1]
j = n - 1
while j > 0 and array[j - 1] > item:
	array[j] = array[j - 1]
	j -= 1
	[print(val, end=' ') for val in array]
	print()
array[j] = item
[print(val, end=' ') for val in array]
print()