Wprowadzenie
Sortowanie przez zliczanie (counting sort) jest jednym z najszybszych algorytmów sortowania danych (szybszy nawet niż QuickSort), a przy tym bardzo prostym do wytłumaczenia. Zostało wynalezione w 1954 r. przez H.H. Sewarda. Algorytm ten działa w czasie O(n), tak więc jest to sortowanie w czasie liniowym. Mimo swoich zalet, sortowanie przez zliczanie ma swoje dwie poważne wady. Po pierwsze - do tego sortowania potrzebna jest dodatkowa pamięć(czyli nie jest to sortowanie w miejscu), a po drugie - tym sposobem można sortować tylko liczby całkowite z określonego przedziału. Nie wiem dlaczego, ale algorytm ten mimo swojej prostoty nie jest powszechnie znany, a tym bardziej używany.
Przykład
Wyobraźmy sobie, że mamy do posortowania następującą tablicę liczb:
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
Moglibyśmy posortować ją jedną ze znanych metod, jednakże nie lepiej jest policzyć ile jest elementów tablicy z wartością 0 i ile z wartością 1, a potem zapisać odpowiednią ilość pól w tej tablicy? W powyższym przypadku otrzymujemy: 5 elementów z wartością 0 i również 5 z wartością 1. Teraz po prostu zapisujemy 5 pierwszych elementów tablicy wartością 0 i 5 następnych wartością 1. W ten sposób otrzymujemy:
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
I po wszystkim. Tablica jest już jest posortowana! Proste, co? Jednakże ten przypadek był wyidealizowany. W prawdziwym sortowaniu liczby nie będą przyjmować tylko wartości 0, czy 1. Zakres wartości elementów tablicy przeznaczonej do sortowania może być dużo większy. W powyższym przypadku do zliczania potrzebne były nam tylko dwie zmienne (jedna do liczenia ilości 0, a druga - ilości 1). W prawdziwym sortowaniu na zliczanie elementów należy przeznaczyć tablicę o wielkości równej rozpiętości liczb z tablicy do posortowania. Na przykład, gdy elementami tablicy przeznaczonej do sortowania są elementy typu Word lub Integer (short int w C) to tablica do zliczania powinna zawierać 65536 elementów (tyle bowiem różnych wartości może przyjąć zmienna Word, czy Integer). To jest właśnie powód, dlaczego sortowaniem przez zliczanie nie można posortować liczb rzeczywistych, a jedynie liczby całkowite. Proszę zwrócić uwagę na to, że sortowanie przez zliczanie nie wykonuje żadnych porównań. Jego ważną własnością jest jego stabilność.