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.

Spis treści

1 Przykładowa implementacja w języku C
- 1.1 Wersja uproszczona
- 1.2 Wersja standardowa
2 Linki zewnętrzne

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

[edytuj] Wersja uproszczona

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

[edytuj] Wersja standardowa

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
  }