Lekcja: "Algorytmy sortujące - sortowanie przez scalanie, sortowanie przez zliczanie"
Przykład counting sort cd.
W zasadzie proces sortowania moglibyśmy zakończyć na tym etapie, jednak jeżeli chcemy aby nasz algorytm był stabilny podczas sortowania wartości „kluczy” (czyli takich wartości, które są przypisane pewnym większym strukturom danych) musimy wykonać obieg dystrybucyjny.
Obieg dystrybucyjny ma za zadanie obliczyć dystrybuantę, czyli ilość elementów mniejszych lub równych od danej wartości.
W tym celu ponownie przeglądamy zbiór danych wejściowych idąc od ostatniego elementu do pierwszego – inaczej algorytm nie byłby stabilny. Po kolei, każdy element umieszczamy w zbiorze wynikowym na pozycji równej zawartości licznika dla tego elementu. Po wykonaniu tej operacji licznik zmniejszamy o 1.
Na przykładzie będzie to wyglądało w następujący sposób: np. dla liczby 4 – jej licznik ma zawartość [4:11] – dlatego liczbę 4 umieszczamyw zbiorze wynikowym na pozycji 11 i zmniejszamy stan licznika o 1, w wyniku czego otrzymamy [4:10]. Kolejna liczba 4 trafi na pozycję 10, itd.
Dla liczby 6 wartość licznika wynosi [6:16] – czyli 6 będzie na 16 pozycji, zmniejszamy licznik o 1i otrzymujemy [6:15].
Analogicznie postępujemy ze wszystkimi liczbami w sortowanym zbiorze, do momentu za zbiór zostanie całkowicie uporządkowany w sposób rosnący.
