Sortowanie przez zliczanie

Z Wikipedii

Sortowanie przez zliczanie – metoda sortowania, wymagająca spełnienia pewnych założeń wobec sortowanych danych. Jej główną zaletą jest liniowa złożoność obliczeniowa algorytmu – O(n+k) (n – oznacza liczebność zbioru, k – liczbę różnych elementów). 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).

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.

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;

Idea algorytmu polega na sprawdzeniu ile wystąpień danego klucza występuje w sortowanej tablicy.

[edytuj] Przykładowa implementacja w języku C

[edytuj] Wersja uproszczona

Wersja ta, działa jedynie na danych całkowitoliczbowych. W przykładzie k określa zakres występujących liczb.

const int k = 77; // elementami tablicy T są liczby całkowite z 
                              // z przedziału 1..77
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]-1]++;             // 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]-1]-1] = T[i];   // wstawienie elementu na odpowiednią pozycję
     --TPom[T[i]-1];            // aktualizacja TPom
  }

[edytuj] Linki zewnętrzne

• Aplet w języku Java demonstrujący działanie algorytmu