Sortowanie

Limit pamięci: 32 MB

Twoim zadaniem będzie posortowanie ciągu liczb całkowitych. Jednakże nie podajemy ograniczenia na liczbę elementów tego ciągu. Napisz program, który będzie wczytywał liczby ze standardowego wejścia, tak długo, aż wczytaną liczbą będzie 0 oraz wypisze wszystkie wczytane liczby w porządku niemalejącym.

Zadanie

Napisz program, który:

  • wczyta ze standardowego ciąg liczb całkowitych nieujemnych zakończony liczbą 0,
  • wypisze wszystkie wszystkie liczby z tego ciągu (wraz z końcowym zerem) w porządku niemalejącym.

Wejście

Wejście zawiera pewną ilość liczb całkowitych nieujemnych, nie większych niż . Każda z tych liczb zapisana będzie w osobnym wierszu. W ostatnim wierszu zapisana będzie liczba 0. Możesz założyć, że liczba 0 nie pojawi się nigdzie wcześniej wśród podanych elementów.

Wyjście

Wyjście Twojego programu powinno stanowić dokładnie tyle samo wierszy, ile liczb było na standardowym wejściu. Liczby te muszą być wypisane w porządku niemalejącym.

Przykład

Dla danych wejściowych:

5
2
2
6
1
0

poprawną odpowiedzią jest:

0
1
2
2
5
6

Wskazówka

W rozwiązaniu tego zadania polecamy zastosować algorytm sortowania przez wstawianie, wykorzystujący listę jednokierunkową.