Sortowanie przez zliczanie

Zadanie 7 z 7 · rozdział 21Trudność: 1 z 3sortingcounting-sortlist

Treść zadania

Napisz funkcję sortowanie_przez_zliczanie(lista, k), która sortuje rosnąco listę liczb całkowitych z przedziału $[0, k]$ algorytmem sortowania przez zliczanie:

  1. Utwórz listę liczności licznosci długości $k + 1$ wypełnioną zerami.
  2. Przejdź po liście i dla każdego elementu $x$ zwiększ licznosci[x] o 1. Po tym kroku licznosci[v] to liczba wystąpień wartości $v$.
  3. Wypisz listę liczności.
  4. Zbuduj wynik: dla kolejnych wartości $v = 0, 1, \dots, k$ dopisz do niego $v$ dokładnie licznosci[v] razy. Zwróć wynik.

Algorytm w ogóle nie porównuje elementów ze sobą.

Dane wejściowe

  • 1. linia: liczba elementów $n$
  • 2. linia: $n$ liczb całkowitych z przedziału $[0, k]$ oddzielonych spacjami
  • 3. linia: liczba całkowita $k$ — największa możliwa wartość

Dane wyjściowe

  • 1. linia: lista liczności (długości $k + 1$) w formacie listy Pythona
  • 2. linia: posortowana lista w formacie listy Pythona

Ograniczenia

  • $1 \le n \le 100$
  • $0 \le k \le 100$

Uwagi

Uwagi o algorytmie:

  • Złożoność czasowa: $O(n + k)$ — dla małych wartości $k$ to szybciej niż $O(n \log n)$ najlepszych algorytmów opartych na porównaniach.
  • Algorytm nadaje się tylko do sortowania liczb całkowitych z niewielkiego zakresu (lista liczności ma $k + 1$ elementów).

Przykład

Wejście
8
3 0 5 3 1 0 3 5
5
Wyjście
[2, 1, 0, 3, 0, 2]
[0, 0, 1, 3, 3, 3, 5, 5]

Wartość 0 występuje 2 razy, 1 — raz, 2 — ani razu, 3 — 3 razy, 4 — ani razu, 5 — 2 razy.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 21

Zadania w tym rozdziale polegają na samodzielnym zaimplementowaniu klasycznych algorytmów sortowania i wyszukiwania. Żeby było widać, że program naprawdę wykonuje dany algorytm, w każdym zadaniu wypisujesz stany pośrednie — listę po kolejnych krokach algorytmu albo kolejno sprawdzane pozycje.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Wejście ma zawsze tę samą postać: w 1. linii liczba elementów $n$, w 2. linii $n$ liczb całkowitych oddzielonych spacjami. Jeśli algorytm potrzebuje dodatkowej wartości (np. szukanego klucza), znajduje się ona w 3. linii.
  • Listę wypisuj w formacie Pythona — dokładnie tak, jak robi to print(lista), np. [1, 2, 4, 6, 27].
  • Sortujemy zawsze rosnąco (niemalejąco — liczby mogą się powtarzać).
  • Zaimplementuj algorytm samodzielnie. Nie używaj sorted(), list.sort(), list.index(), operatora in na liście ani innych gotowych funkcji sortujących i wyszukujących.
  • 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
0
0
Oczekiwane wyjście
[1]
[0]

Test 2

Nie uruchomiono
Wejście
3
4 4 4
4
Oczekiwane wyjście
[0, 0, 0, 0, 3]
[4, 4, 4]

Test 3

Nie uruchomiono
Wejście
5
9 0 9 0 5
9
Oczekiwane wyjście
[2, 0, 0, 0, 0, 1, 0, 0, 0, 2]
[0, 0, 5, 9, 9]

Test 4

Nie uruchomiono
Wejście
6
1 2 3 2 1 0
3
Oczekiwane wyjście
[1, 2, 2, 1]
[0, 1, 1, 2, 2, 3]

Test 5

Nie uruchomiono
Wejście
4
7 3 10 1
10
Oczekiwane wyjście
[0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1]
[1, 3, 7, 10]
Uruchom z własnymi danymi