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.
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