Sortowanie przez zliczanie

Z Wikipedii

Sortowanie przez zliczanie – specyficzna 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.

Przykładowy program (wersja prostsza) w języku C:

const int k = 77;             // elementami tablicy T są liczby całkowite z 
                              // z przedziału 1..77
const int n = 1000;
int T[n];                     // sortowana tablica
int TPom[k];                  // zawiera liczbę elementów o danej wartości

int i;  // pomocnicza zmienna (indeks)

// wyzerowanie pomocniczej tablicy
  for (i = 0 ; i < k ; i++)
    TPom[i] = 0;

// zliczenie elementów o danej wartości
  for (i = 0 ; i < n ; i++)
    TPom[T[i]-1] += 1;

// w tym miejscu możemy przepisać dane znowu do tablicy początkowej
  int j, l = 0;
  for (i = 0 ; i < k ; i++)
    for (j = 0 ; j < TPom[i] ; j++)
       T[l++] = i+1;      // miejsce w tablicy pomocniczej określa wartość zmiennej

Przykładowy program (wersja standardowa) w języku C:

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