Algorytmy 1

Sortowanie przez wybieranie

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 wybieranie (ang. selection sort), tzn. zastosuj poniższy algorytm:

// Cormen et al. - Introduction to Algorithms
SELECTION-SORT(a, n)
for j=1 to n-1
	minIndex = j
	for i=j+1 to n
		if a[i] < a[minIndex]
		   minIndex = i
	swap a[j] with a[minIndex]

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
1 2 4 6 5 3
1 2 4 6 5 3
1 2 3 6 5 4
1 2 3 4 5 6
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