**Sortowanie przez zliczanie **– metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy. Algorytm zakłada, że klucze elementów należą do skończonego zbioru (np. są to liczby z całkowite przedziału X..Y), co ogranicza możliwości jego zastosowania. Główną zaletą tej metody jest liniowa złożoność obliczeniowa algorytmu – O(n+z) (n – oznacza liczebność zbioru, z – 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 skali ocen (0-10) wynosi (10-0) + 1 =11) Największymi ograniczeniami algorytmu są konieczność uprzedniej znajomości zakresu danych i złożoność pamięciowa (wymaga dodatkowo O(z) pamięci) . Algorytm możemy zawsze zmodyfikować by przechowywał dane na dysku twardym komputera lecz wtedy stracimy na wydajności co będzie spowodowane maksymalną przepustowością dysku co przy dzisiejszych dyskach SSD stanowi mniejsze ograniczenie w porównaniu do dysków HDD.

Zasada działania
Polega na liczeniu, ile razy dana liczba występuje w ciągu, który mamy posortować. Następnie tworzymy nowy ciąg, korzystając z danych zebranych wcześniej. Posortujmy ciąg {6,2,1,4,2,1,3}

Dane wejściowe
d[] – zbiór elementów do posortowania. Każdy element posiada pole klucz, wg którego dokonuje się sortowania. Pole klucz jest liczbą całkowitą. Indeksy elementów rozpoczynają się od 1.

n – ilość elementów w zbiorze d[].

kmin - minimalna wartość klucza.

kmax - maksymalna wartość klucza.

Dane wyjściowe

b[] – zbiór z posortowanymi elementami ze zbioru d[]. Indeksy elementów rozpoczynają się od 1.

Zmienne pomocnicze

i – zmienna dla pętli iteracyjnych

L[] -tablica liczników wartości kluczy. Elementy są liczbami całkowitymi. Indeksy przybierają kolejne wartości od k_min do k_max.

Lista kroków
1: Dla i=k_min, k_min+1,…,k_max: wykonuj L[i]=0;

2: Dla i=1,2,…,n: wykonuj L[d[i].klucz]==L[d[i].klucz]+1;

3:Dla i=k_min + 1, k_min+2,…,k_max:wykonuj L[i]=L[i]+L[i-1]

4: Dla i=n,n-1,…,1: wykonuj krok 5…6

5: b[L[D[i].klucz]] =d[i]

6: L[d[i].klucz]=L[d[i].klucz]-1

7: Zakończ

<img src="http://cpp.lisart.pl/wp-content/uploads/2014/09/couting_sort.jpg>

Kod źródłowy funkcji sortującej dane typu całkowitego int w języku C++.

struct dane {

unsigned klucz;

char wyraz[3];

} d[N],b[N];

void countig_sort(int KMIN,int KMAX, int N, int * L[], dane * d[], dane * b[])
{
//Zerujemy liczniki
for(i = KMIN; i <= KMAX; i++) L[i - KMIN] = 0;
//Zliczamy wystąpienia kluczy
for(i = 0; i < N; i++) L[d[i].klucz - KMIN]++;
//Obliczamy pozycje końcowe
for(i = KMIN + 1; i <= KMAX; i++) L[i - KMIN] += L[i - KMIN - 1]; 
// Przepisujemy elementy z d[] do b[]
for(i = N - 1; i >= 0; i–) b[(L[d[i].klucz - KMIN]–) - 1] = d[i];
} 

Chcesz być na bieżąco ?

Polub nas!