Sortowanie listy 0/1/2

Zadanie 6 z 9 · rozdział 22Trudność: 2 z 3sortcounting

Treść zadania

Wczytaj listę składającą się wyłącznie z liczb 0, 1 i 2 i posortuj ją rosnąco.

Dane wejściowe

  • 1. linia: liczba elementów $N$
  • 2. linia: $N$ liczb (każda to 0, 1 albo 2) oddzielonych spacjami

Dane wyjściowe

  • 1. linia: posortowana lista — liczby oddzielone pojedynczymi spacjami

Ograniczenia

  • $1 \le N \le 1000$

Uwagi

  • Zadanie da się rozwiązać w czasie $O(N)$, bez sortowania. Najprościej policzyć zera, jedynki i dwójki, a potem wypisać odpowiednio wiele zer, jedynek i dwójek (to sortowanie przez zliczanie z rozdziału 21).
  • Ambitniejszy wariant działa w miejscu, w jednym przejściu po liście: trzymaj trzy indeksy — koniec obszaru zer, bieżący element i początek obszaru dwójek — i zamieniaj elementy miejscami (tzw. problem flagi holenderskiej).

Przykład

Wejście
7
1 0 1 2 2 0 1
Wyjście
0 0 1 1 1 2 2

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 22

Zadania w tym rozdziale pokazują, jak sortować w praktyce: napisy, słowa, pary, obiekty — często według własnego kryterium. Tutaj wolno (a nawet warto) korzystać z wbudowanych narzędzi Pythona: sorted(), list.sort() i parametru key=.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Jeśli wejściem jest napis — wczytaj całą linię (łącznie ze spacjami).
  • Jeśli wejściem jest lista — najpierw podana jest liczba elementów $N$, a potem elementy (w jednej linii albo w kolejnych liniach — zależnie od zadania).
  • Napisy porównujemy tak jak Python, czyli według kodów znaków Unicode: wielkie litery są „mniejsze” od małych ('Z' < 'a'), a polskie litery są „większe” od wszystkich liter alfabetu łacińskiego ('z' < 'ą').
  • Sortowanie w Pythonie (sorted(), list.sort()) jest stabilne: elementy równe według kryterium sortowania zachowują kolejność z wejścia. Korzystają z tego zadania, w których mogą wystąpić remisy.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
2
Oczekiwane wyjście
2

Test 2

Nie uruchomiono
Wejście
5
2 2 2 1 0
Oczekiwane wyjście
0 1 2 2 2

Test 3

Nie uruchomiono
Wejście
3
0 0 0
Oczekiwane wyjście
0 0 0

Test 4

Nie uruchomiono
Wejście
6
2 1 0 2 1 0
Oczekiwane wyjście
0 0 1 1 2 2

Test 5

Nie uruchomiono
Wejście
10
0 2 2 0 1 1 2 2 1 1
Oczekiwane wyjście
0 0 1 1 1 1 2 2 2 2

Test 6

Nie uruchomiono
Wejście
4
1 2 1 1
Oczekiwane wyjście
1 1 1 2
Uruchom z własnymi danymi