Loading AI tools
Z Wikipedii, wolnej encyklopedii
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[1].
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Pamięciowa |
lub w zależności od implementacji |
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].
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.
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)[potrzebny przypis].
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)[potrzebny przypis].
Istnieją dwie implementacje algorytmu[potrzebny przypis]:
Wersja ta sortuje n-elementową tablicę liczb całkowitych[potrzebny przypis].
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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.