Sortowanie przez zliczanie

Sortowanie przez zliczanie w ogóle nie porównuje wartości. Jeśli wiesz, że każda wartość jest liczbą całkowitą, powiedzmy, od 1 do 40, możesz po prostu policzyć, ile jest każdej, i z tych zliczeń ustalić, gdzie należy każda z nich. Przy małym zakresie to niemal najszybsze możliwe sortowanie.

Słupki listy, pasek liczników pokazujących, ile razy występuje każda wartość, i wiersz bufora, w którym każda wartość ma własny blok
Słupki listy, pasek liczników pokazujących, ile razy występuje każda wartość, i wiersz bufora, w którym każda wartość ma własny blok

Zliczanie

Znajdź najmniejszą i największą wartość i utwórz jeden licznik dla każdej wartości pomiędzy nimi, każdy ustawiony na zero. Przeczytaj listę raz od początku do końca i dodaj jeden do licznika każdej napotkanej wartości. Liczniki tworzą teraz histogram: ile jest jedynek, ile dwójek i tak dalej. Przy n wartościach i k licznikach zajmuje to n kroków.

Sumowanie

Wartości równe najmniejszej wartości są pierwsze, więc ich blok zaczyna się na miejscu 1. Blok następnej wartości zaczyna się tuż po nich i tak dalej: każdy blok zaczyna się po sumie wszystkich wcześniejszych zliczeń. Te sumy narastające, zwane sumami prefiksowymi, zamieniają histogram w mapę posortowanej listy. Zajmuje to k kroków.

Umieszczanie

Przeczytaj listę drugi raz i przenieś każdą wartość na następne wolne miejsce w jej bloku. Ponieważ wartości są przenoszone w kolejności występowania, równe wartości zachowują pierwotną kolejność: sortowanie przez zliczanie jest stabilne. Skopiuj bufor z powrotem i lista jest posortowana. Aplikacja pokazuje, jak każdy licznik znowu maleje, gdy jego wartości trafiają na miejsca.

Przykład

Weź 4, 1, 3, 4, 2, 1, 4. Liczniki dla wartości od 1 do 4 kończą na 2, 1, 1 i 3. Sumowanie daje bloki: jedynki na miejscach 1 i 2, dwójka na miejscu 3, trójka na miejscu 4, a czwórki na miejscach od 5 do 7. Umieszczenie wartości w kolejności z listy daje 1, 1, 2, 3, 4, 4, 4: 7 zliczonych wartości, 14 przeniesień, 4 liczniki i żadnych porównań.

Kiedy go używać

Całkowita praca rośnie z n + k. Gdy k jest małe w porównaniu z n, jak tysiąc wyników egzaminu od 0 do 100, sortowanie przez zliczanie jest szybsze niż każde sortowanie przez porównania, które potrzebuje około n log₂ n porównań. Przy szerokim zakresie jest rozrzutne: kilka wartości rozrzuconych aż do miliona wymaga miliona liczników. Sortowanie pozycyjne rozwiązuje to, uruchamiając sortowanie przez zliczanie raz dla każdej cyfry, więc każdy przebieg potrzebuje tylko dziesięciu liczników. Harold Seward opisał sortowanie przez zliczanie, razem z sortowaniem pozycyjnym, w 1954 roku.

Wypróbuj w aplikacji

Otwórz aplikację i naciśnij Krok. Pasek między listą a wierszem bufora pokazuje jeden licznik na wartość. Obserwuj, jak liczniki rosną podczas czytania listy, bloki pojawiają się w buforze po zsumowaniu zliczeń, a liczniki znów maleją, gdy wartości trafiają na miejsca. Wybierz mało różnych wartości, aby zobaczyć duże bloki, albo wpisz liczby daleko od siebie, aby zobaczyć, ilu liczników wymaga szeroki zakres.

Często zadawane pytania

Jaka jest złożoność czasowa sortowania przez zliczanie?

O(n + k) dla n wartości i k możliwych wartości oraz O(n + k) dodatkowej pamięci na liczniki i bufor.

Dlaczego sortowanie przez zliczanie nie zawsze jest najszybsze?

Bo jego koszt zależy od zakresu wartości, a nie tylko od ich liczby. Jeśli zakres jest dużo większy niż lista, większość liczników zostaje na zerze, a czas i pamięć idą na marne.

Czy sortowanie przez zliczanie radzi sobie z liczbami ujemnymi?

Tak. Liczniki biegną od najmniejszej wartości do największej, więc odejmij najmniejszą wartość, aby otrzymać indeks licznika. Aplikacja robi to samo.

Czy sortowanie przez zliczanie jest stabilne?

Tak, o ile wartości są przenoszone w kolejności z listy na następne wolne miejsce w swoim bloku. Od tego zależy sortowanie pozycyjne.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj sortowanie przez zliczanie