Sortowanie przez zliczanie

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Sortowanie przez zliczanie – metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy[1].

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[1].

Zalety i wady[edytuj | edytuj kod]

Główną zaletą tej metody jest liniowa złożoność obliczeniowa algorytmu – O(n+k)[2] (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)[potrzebne źródło].

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)[potrzebne źródło].

Implementacje[edytuj | edytuj kod]

Istnieją dwie implementacje algorytmu[potrzebne źródło]:

  • 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++[edytuj | edytuj kod]

Wersja ta sortuje n-elementową tablicę liczb całkowitych[potrzebne źródło].

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ń elementów o kluczu 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

Przypisy

Bibliografia[edytuj | edytuj kod]

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

Linki zewnętrzne[edytuj | edytuj kod]