Algorytmy 1

Sortowanie przez wstawianie

Limit czasu: 1s | Limit pamięci: 64MB

Dany jest ciąg liczb $a_1, a_2, \ldots, a_n$. Posortuj te elementy za pomocą algorytmu sortowania przez wstawianie (ang. insertion sort), tzn. zastosuj poniższy algorytm:

// Cormen et al. - Introduction to Algorithms
INSERTION-SORT(a, n)
for i=2 to n
	key = a[i]
	// insert a[i] into the sorted subarray a[1..i-1]
	j = i-1
	while j>0 and a[j]>key
		a[j+1] = a[j]
		j = j-1
	a[j+1] = key

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę $n$. Drugi wiersz zawiera $n$ liczb $a_i$.

Wyjście

Pierwszy wiersz wyjścia zawiara ciąg $n$ elementów $a_i$ w takiej kolejności, w jakiej pojawiły się one na wejściu. Kolejne $n-1$ lini zawiera ciąg elementów $a_i$ w kolejności, w jakiej znajdą się one po każdym przebiegu pętli for.

Ograniczenia

$1 \le n \le 100$
$-10^9 \le a_i \le 10^9$

Przykłady

Wejście 1

6
5 2 4 6 1 3

Wyjście 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

Wejście 2

3
1 2 3

Wyjście 2

1 2 3
1 2 3
1 2 3

Wejście 3

1
42