Czym jest sortowanie przez zliczanie?
Sortowanie przez zliczanie to algorytm sortowania, który nie porównuje elementów parami. Zamiast tego zlicza, ile razy występuje każda wartość, a następnie odtwarza posortowaną tablicę na podstawie tych zliczeń.
Algorytm jest bardzo szybki, gdy sortowane wartości są liczbami całkowitymi z niewielkiego, znanego zakresu, np. od 0 do 100.
Złożoność
Typowa złożoność czasowa wynosi:
O(n + k), gdzie:n- liczba elementów do posortowania,k- rozmiar zakresu możliwych wartości.
Jeżeli zakres k jest mały lub traktowany jako stały, uproszczony zapis to O(n). Dlatego w wielu zadaniach egzaminacyjnych sortowanie przez zliczanie jest wskazywane jako bardzo efektywne dla dużych zbiorów danych.
Przykład działania
Dane wejściowe:
[3, 1, 2, 3, 1]
Zliczenia:
1 -> 2 razy
2 -> 1 raz
3 -> 2 razy
Wynik:
[1, 1, 2, 3, 3]
Zalety
- bardzo dobra wydajność dla odpowiednich danych,
- może działać w czasie liniowym,
- dobrze sprawdza się dla liczb całkowitych z ograniczonego zakresu.
Ograniczenia
- wymaga dodatkowej pamięci na tablicę zliczeń,
- nie nadaje się bezpośrednio do dowolnych danych, np. napisów bez mapowania,
- jest nieopłacalne, gdy zakres wartości jest bardzo duży w stosunku do liczby elementów.