Sortowanie przez zliczanie

Sortowanie przez zliczanie

Rodzaj	Sortowanie
Struktura danych	Tablica, lista
Złożoność
Czasowa	$O(n+k)$
Pamięciowa	$O(n)$ lub $O(n+k)$ w zależności od implementacji

Sortowanie przez zliczanie (ang. counting sort) – 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.

Opis algorytmu

Na początku działania algorytmu ustalany jest przedział wartości, które zależą od wartości wszystkich elementów w sekwencji, która ma być posortowana. Dla przykładu, sekwencja v liczb całkowitych [100, 2, 0, 150, 2, 3, 0] tworzy przedział [min(v), max(v)] = [0, 150] wynoszący łącznie 151 elementów; z kolei v' o wartościach [15, 6, 11, 10] tworzy przedział [6, 15] z dziesięcioma elementami. W momencie, gdy przedział nie jest znany, można posłużyć się minimalnymi i maksymalnymi wartościami typów elementów w v (np. dla sekwencji, gdzie każdy element ma typ unsigned char (8 bitów) jest to [0, 255]).

Dla każdego elementu z utworzonego przedziału obliczana jest liczba jego wystąpień w wejściowej sekwencji v, tzn. tworzony jest histogram dla elementów sekwencji wejściowej. Na podstawie utworzonego histogramu generowana jest sekwencja wyjściowa, czyli posortowane elementy. Generowanie polega na iteracji po kolejnym elemencie w histogramie (który również jest sekwencją) oraz konkatenacji do sekwencji wynikowej tymczasowej sekwencji tylu elementów o danej wartości ile wskazuje histogram dla danego elementu. Początkowa sekwencja wynikowa jest pusta.

Sortowanie przez zliczanie można rozumieć jako złożenie dwóch funkcji, h generującej histogram, oraz g generującej sekwencję wyjściową na podstawie histogramu: g(h(v)). Złożenie w wyniku daje posortowaną sekwencję elementów wejściowych. Przykład:

       v = [0, 3, 2, 3, 3, 3] -- dane wejściowe
h(v) = z = [1, 0, 1, 4]       -- histogram (w tym przypadku indeks określa wartość elementu w v)
   
   -- iteracja po histogramie, ++ oznacza konkatenację sekwencji
   []                                     -- start: pusta sekwencja wyjściowa
   []     ++ [0]    = [0]                 -- element o wartości 0 w sekwencji wejściowej v występuje z[0] razy (=1)
   [0]    ++ []     = [0]                 -- element o wartości 1 w sekwencji wejściowej v występuje z[1] razy (=0)
   [0]    ++ [2]    = [0, 2]              -- element o wartości 2 w sekwencji wejściowej v występuje z[2] razy (=1)
   [0, 2] ++ [3, 3] = [0, 2, 3, 3, 3, 3]  -- element o wartości 3 w sekwencji wejściowej v występuje z[3] razy (=4)
   
wynik: [0, 2, 3, 3, 3, 3]

W powyższym przykładzie wykorzystano indeks (numerowany od zera) jako wartość elementu z wejściowej sekwencji v do pobrania danych z wygenerowanego histogramu z. W przypadku, gdy przedział wartości nie zawiera w sobie wartości 0, lub gdy histogram nie może być indeksowany w z góry zdefiniowany sposób, wymagana jest dodatkowa funkcja, która zapewni dostęp do z przy pomocy elementu z v. Zadanie takiej funkcji zwykle sprowadza się do manipulacji indeksami przy pomocy podstawowej arytmetyki.

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 całkowitych: 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) dodatkowej 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..76
const int n = 1000;
int T[n]; // tablica zawierająca elementy do posortowania
int Tp[n]; // tablica zawierająca elementy posortowane
int 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ń kolejnego elementu o wartości T[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

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.

Linki zewnętrzne

• Aplet w języku Java demonstrujący działanie algorytmu. users.cs.cf.ac.uk. [zarchiwizowane z tego adresu (2013-06-02)].