Sortowanie przez zliczanie – metoda
sortowania
danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy.
Algorytm zakłada, że klucze elementów należą do skończonego zbioru (np. są to
liczby całkowite
z przedziału 0..100), co ogranicza możliwości jego zastosowania.
Zalety i wady
Główną zaletą tej metody jest liniowa
złożoność obliczeniowa
algorytmu
– O(n+k) (n – oznacza liczebność zbioru, k – rozpiętość danych, czyli w przypadku liczb: powiększoną o 1 różnicę między maksymalną, a minimalną wartością, np. rozpiętość liczb w Dużym Lotku wynosi (49-1) + 1 = 49).
Największymi ograniczeniami algorytmu są konieczność uprzedniej znajomości zakresu danych i
złożoność pamięciowa
(wymaga dodatkowo O(k) lub O(n+k) pamięci).
Implementacje
Istnieją dwie implementacje algorytmu:
- prostsza – sortująca in situ (w miejscu), zakłada, że elementy o równych kluczach są nierozróżnialne, nie mogą zatem być to klucze danych (każdy z nich jest bowiem powiązany z przenoszoną wartością – zatem, mimo iż są one równe, muszą pozostawać rozróżnialne);
- standardowa – gwarantuje stabilność i nie wymaga dodatkowego założenia. Potrzebuje natomiast O(n) więcej pamięci;
Przykładowa implementacja w
języku C++
Wersja ta sortuje n-elementową tablicę liczb całkowitych.
const int k = 77; // elementami tablicy T są liczby całkowite z // z przedziału 0..76const int n = 1000;int T[n]; // tablica zawierająca elementy do posortowaniaint Tp[n]; // tablica zawierająca elementy posortowaneint TPom[k]; // zawiera liczbę elementów o danej wartości int i; // zmienna pomocnicza for(i = 0 ; i < k ; ++i) TPom[i] = 0; // zerowanie tablicy for(i = 0 ; i < n ; ++i) ++TPom[T[i]]; // po tych operacjach TPom[i] będzie zawierała // liczbę wystąpień elementów o kluczach mniejszych od i for(i = 1 ; i < k ; ++i) TPom[i] += TPom[i-1]; // teraz TPom[i] zawiera pozycje w posortowanej // tablicy ostatniego elementu o kluczu i for(i = n-1 ; i >= 0 ; --i) Tp[--TPom[T[i]]] = T[i]; // wstawienie elementu na odpowiednią pozycję // i aktualizacja TPom
Linki zewnętrzne
