Informatyka dla klas II

Pierwszy element d[0] nie posiada poprzednika (ang. predecessor - elementu poprzedzającego w ciągu). Ostatni element d[n-1] nie posiada następnika (ang. successor - elementu następnego w ciągu). Wszystkie pozostałe elementy posiadają poprzedniki i następniki.

Drzewo binarne jest hierarchiczną strukturą danych, którego elementy będziemy nazywali węzłami (ang. node) lub wierzchołkami. W hierarchii liniowej każdy element może posiadać co najwyżej jeden następnik. W drzewie binarnym każdy węzeł może posiadać dwa następniki (stąd pochodzi nazwa drzewa - binarny = dwójkowy, zawierający dwa elementy), które nazwiemy potomkami. dziećmi lub węzłami potomnymi danego węzła (ang. child node).

Węzły są połączone krawędziami symbolizującymi następstwo kolejnych elementów w strukturze drzewa binarnego. Według rysunku po prawej stronie węzeł A posiada dwa węzły potomne: B i C. Węzeł B nosi nazwę lewego potomka (ang. left child node), a węzeł C nosi nazwę prawego potomka (ang. right child node).

Z kolei węzeł B posiada węzły potomne D i E, a węzeł C ma węzły potomne F i G. Jeśli dany węzeł nie posiada dalszych węzłów potomnych, to jest w strukturze drzewa binarnego węzłem terminalnym. Taki węzeł nosi nazwę liścia (ang. leaf node). Na naszym rysunku liśćmi są węzły terminalne D, E, F i G.

Rodzicem, przodkiem (ang. parent node) lub węzłem nadrzędnym będziemy nazywać węzeł leżący na wyższym poziomie hierarchii drzewa binarnego. Dla węzłów B I C węzłem nadrzędnym jest węzeł A. Podobnie dla węzłów D i E węzłem nadrzędnym będzie węzeł B, a dla F i G będzie to węzeł C.

Węzeł nie posiadający rodzica nazywamy korzeniem drzewa binarnego (ang. root node). W naszym przykładzie korzeniem jest węzeł A. Każde drzewo binarne, które zawiera węzły posiada dokładnie jeden korzeń.

Zastosujmy następujące odwzorowanie:

• Element d[0] będzie zawsze korzeniem drzewa.
• i-ty poziom drzewa binarnego wymaga 2^i-1 węzłów. Będziemy je kolejno pobierać z tablicy.

Otrzymamy w ten sposób następujące odwzorowanie elementów tablicy w drzewo binarne:

Dla węzła k-tego wyprowadzamy następujące wzory:

węzły potomne mają indeksy równe: 2k + 1 - lewy potomek 2k + 2 - prawy potomek węzeł nadrzędny ma indeks równy [(k - 1) / 2] (dzielenie całkowitoliczbowe)

Sprawdź, iż podane wzory są również spełnione w drzewach binarnych o większych rozmiarach niż prezentuje nasz przykład (pomocna może być kartka papieru).

Przykład:

Skonstruować drzewo binarne z elementów zbioru {7 5 9 2 4 6 1}

Operacja	Opis
7 5 9 2 4 6 1	Konstrukcję drzewa binarnego rozpoczynamy od korzenia, który jest pierwszym elementem zbioru, czyli liczbą 7.
7 5 9 2 4 6 1	Do korzenia dołączamy dwa węzły potomne, które leżą obok w zbiorze. Są to dwa kolejne elementy, 5 i 9.
7 5 9 2 4 6 1	Do lewego węzła potomnego (5) dołączamy jego węzły potomne. Są to kolejne liczby w zbiorze, czyli 2 i 4.
7 5 9 2 4 6 1	Pozostaje nam dołączyć do prawego węzła ostatnie dwa elementy zbioru, czyli liczby 6 i 1. Drzewo jest kompletne.

 

Warunek ten gwarantuje nam, iż każdy element tablicy będzie reprezentował pewien węzeł w drzewie binarnym - czyli w tej strukturze nie wystąpią dziury.

Drzewo po lewej stronie nie posiada węzła d[6]. Ale posiada wszystkie węzły od d[0] do d[5], jest zatem zrównoważone i uporządkowane. Można je bez problemu przedstawić za pomocą tablicy elementów od d[0] do d[5].

Drzewo po prawej stronie nie posiada węzła d[5]. Takiego drzewa nie przedstawimy poprawnie za pomocą tablicy elementów od d[0] do d[6], ponieważ nie mamy możliwości zaznaczenia (bez dodatkowych zabiegów), iż element d[5] nie należy do struktury drzewa. Zatem nie będzie to uporządkowane i zrównoważone drzewo binarne.

W uporządkowanych i zrównoważonych drzewach binarnych bardzo prosto można sprawdzić, czy k-ty węzeł jest liściem. Będzie tak, jeśli węzeł ten nie posiada węzłów potomnych. Zatem, jeśli drzewo binarne składa się z n węzłów, to wystarczy sprawdzić, czy 2k+1 > n-1. Jeśli tak, węzeł jest liściem. Jeśli nie, węzeł posiada potomka o indeksie 2k+1, zatem nie może być liściem.

Na powyższym rysunku zaznaczona została ścieżka biegnąca poprzez węzły {d[0], d[2], d[5], d[12]}. Ścieżka ta zawiera cztery węzły, ma zatem długość równą 3.

Wysokością drzewa binarnego nazwiemy długość najdłuższej ścieżki od korzenia do liścia. W powyższym przykładzie najdłuższa taka ścieżka ma długość 3, zatem zaprezentowane drzewo binarne ma wysokość równą 3.

Dla n węzłów zrównoważone drzewo binarne ma wysokość równą:

h = [log₂n]

Węzeł nadrzędny jest większy lub równy węzłom potomnym (w porządku malejącym relacja jest odwrotna - mniejszy lub równy).

Konstrukcja kopca jest nieco bardziej skomplikowana od konstrukcji drzewa binarnego, ponieważ musimy dodatkowo troszczyć się o zachowanie warunku kopca. Zatem po każdym dołączeniu do kopca nowego węzła, sprawdzamy odpowiednie warunki i ewentualnie dokonujemy wymian węzłów na ścieżce wiodącej od dodanego węzła do korzenia.

Przykład:

Skonstruować kopiec z elementów zbioru {7 5 9 6 7 8 10}

Operacja	Opis
7 5 9 6 7 8 10	Budowę kopca rozpoczynamy od pierwszego elementu zbioru, który staje się korzeniem.
7 5 9 6 7 8 10	Do korzenia dołączamy następny element. Warunek kopca jest zachowany.
7 5 9 6 7 8 10	Dodajemy kolejny element ze zbioru.
	Po dodaniu elementu 9 warunek kopca przestaje być spełniony. Musimy go przywrócić. W tym celu za nowy węzeł nadrzędny wybieramy nowo dodany węzeł. Poprzedni węzeł nadrzędny wędruje w miejsce węzła dodanego - zamieniamy węzły 7 i 9 miejscami.
	Po wymianie węzłów 7 i 9 warunek kopca jest spełniony.
7 5 9 6 7 8 10	Dołączamy kolejny element 6. Znów warunek kopca przestaje być spełniony - zamieniamy miejscami węzły 5 i 6.
	Po wymianie węzłów 5 i 6 warunek kopca jest spełniony.
7 5 9 6 7 8 10	Dołączamy kolejny element 7. Warunek kopca przestaje obowiązywać. Zamieniamy miejscami węzły 6 i 7.
	Po wymianie węzłów 6 i 7 warunek kopca obowiązuje.
7 5 9 6 7 8 10	Dołączamy kolejny węzeł. Powoduje on naruszenie warunku kopca, zatem wymieniamy ze sobą węzły 7 i 8.
	Po wymianie węzłów 7 i 8 warunek kopca znów obowiązuje.
7 5 9 6 7 8 10	Dołączenie ostatniego elementu znów narusza warunek kopca. Zamieniamy miejscami węzeł 8 z węzłem 10.
	Po wymianie węzłów 8 i 10 warunek kopca został przywrócony na tym poziomie. Jednakże węzeł 10 stał się dzieckiem węzła 9. Na wyższym poziomie drzewa warunek kopca jest naruszony. Aby go przywrócić znów wymieniamy miejscami węzły, tym razem węzeł 9 z węzłem 10.
	Po wymianie tych węzłów warunek kopca obowiązuje w całym drzewie - zadanie jest wykonane.

Charakterystyczną cechą kopca jest to, iż korzeń zawsze jest największym (w porządku malejącym najmniejszym) elementem z całego drzewa binarnego.

Poniżej przedstawiamy algorytm konstrukcji kopca z elementów zbioru.

Dane wejściowe

d[ ]	- Zbiór zawierający elementy do wstawienia do kopca. Numeracja elementów rozpoczyna się od 1.
n	- Ilość elementów w zbiorze,  n N

Dane wyjściowe

Zmienne pomocnicze

i	- zmienna licznikowa pętli umieszczającej kolejne elementy zbioru w kopcu,  i  N, i  {2,3,...,n}
j,k	- indeksy elementów leżących na ścieżce od wstawianego elementu do korzenia,  j,k  C
x	- zmienna pomocnicza przechowująca tymczasowo element wstawiany do kopca

Uwaga: przy porządku malejącym należy zmienić drugi warunek w kroku K04 z d[k] < x na d[k] > x.

W tym rozdziale nauczymy się rozbierać kopiec.  Zasada jest następująca:

Przykład:

Dokonaj rozbioru następującego kopca:

Operacja	Opis
9	Rozbiór kopca rozpoczynamy od korzenia, który usuwamy ze struktury kopca. W miejsce korzenia wstawiamy ostatni liść.
			Poprzednia operacja zaburzyła strukturę kopca. Idziemy zatem od korzenia w dół struktury przywracając warunek kopca - przodek większy lub równy od swoich potomków. Praktycznie polega to na zamianie przodka z największym potomkiem. Operację kontynuujemy dotąd, aż natrafimy na węzły spełniające warunek kopca.
8 9	Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
			W nowym kopcu przywracamy warunek kopca.
7 8 9	Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
		W nowym kopcu przywracamy warunek kopca. W tym przypadku już po pierwszej wymianie węzłów warunek koca jest zachowany w całej strukturze.
5 7 8 9	Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
		Przywracamy warunek kopca w strukturze.
4 5 7 8 9	Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
		Przywracamy warunek kopca w strukturze.
2 4 5 7 8 9	Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem.
1 2 4 5 7 8 9	Po wykonaniu poprzedniej operacji usunięcia w kopcu pozostał tylko jeden element - usuwamy go. Zwróć uwagę, iż usunięte z kopca elementy tworzą ciąg uporządkowany.

Operację rozbioru kopca można przeprowadzić w miejscu. Jeśli mamy zbiór d[ ] ze strukturą kopca, to idąc od końca zbioru (ostatnie liście drzewa) w kierunku początku zamieniamy elementy z pierwszym elementem zbioru (korzeń drzewa), a następnie poruszając się od korzenia w dół przywracamy warunek kopca w kolejno napotykanych węzłach.

Dane wejściowe

d[ ]	- Zbiór zawierający poprawną strukturę kopca. Elementy są numerowane począwszy od 1.
n	- Ilość elementów w zbiorze,  n N

Dane wyjściowe

Zmienne pomocnicze

i	- zmienna licznikowa pętli pobierającej kolejne elementy z kopca,  i  N, i  {n-1,...,1}
j,k	- indeksy elementów leżących na ścieżce w dół od korzenia,  j,k N
m	- indeks większego z dwóch elementów potomnych, m N

Jeśli przeczytałeś uważnie poprzednie dwa rozdziały, to zasadę sortowania przez kopcowanie zrozumiesz od razu - w zbiorze tworzymy kopiec, a następnie dokonujemy jego rozbioru. W wyniku wykonania tych dwóch operacji zbiór zostanie posortowany.

Dane wejściowe

d[ ]	- Zbiór zawierający elementy do posortowania, które są numerowane począwszy od 0.
n	- Ilość elementów w zbiorze,  n N

Dane wyjściowe

Zmienne pomocnicze i funkcje

Algorytm

Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach:

1. DZIEL - problem główny zostaje podzielony na podproblemy
2. ZWYCIĘŻAJ - znajdujemy rozwiązanie podproblemów
3. POŁĄCZ - rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego

Idea sortowania szybkiego jest następująca:

prof. Tony Hoare

Sortowanie szybkie zostało wynalezione przez angielskiego informatyka, profesora Tony'ego Hoare'a w latach 60-tych ubiegłego wieku. W przypadku typowym algorytm ten jest najszybszym algorytmem sortującym z klasy złożoności obliczeniowej O(n log n) - stąd pochodzi jego popularność w zastosowaniach. Musimy jednak pamiętać, iż w pewnych sytuacjach (zależnych od sposobu wyboru piwotu oraz niekorzystnego ułożenia danych wejściowych) klasa złożoności obliczeniowej tego algorytmu może się degradować do O(n²), co więcej, poziom wywołań rekurencyjnych może spowodować przepełnienie stosu i zablokowanie komputera. Z tych powodów algorytmu sortowania szybkiego nie można stosować bezmyślnie w każdej sytuacji tylko dlatego, iż jest uważany za jeden z najszybszych algorytmów sortujących - zawsze należy przeprowadzić analizę możliwych danych wejściowych właśnie pod kątem przypadku niekorzystnego - czasem lepszym rozwiązaniem może być zastosowanie wcześniej opisanego algorytmu sortowania przez kopcowanie, który nigdy nie degraduje się do klasy O(n²).

Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy. Dla naszych potrzeb wybierzemy element środkowy:

Dzielenie na partycje polega na umieszczeniu dwóch wskaźników na początku zbioru - i oraz j. Wskaźnik i przebiega przez zbiór poszukując wartości mniejszych od piwotu. Po znalezieniu takiej wartości jest ona wymieniana z elementem na pozycji j. Po tej operacji wskaźnik j jest przesuwany na następną pozycję. Wskaźnik j zapamiętuje pozycję, na którą trafi następny element oraz na końcu wskazuje miejsce, gdzie znajdzie się piwot. W trakcie podziału piwot jest bezpiecznie przechowywany na ostatniej pozycji w zbiorze.

Przykład:

Dla przykładu podzielimy na partycje zbiór:  { 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 }

 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
 i 
 j 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
   i 
 j 

 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
   i 
   j 

 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
     i 
   j 

 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
     i 
     j 

 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
         i 
     j 

 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 
         i 
       j 

 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 
           i 
       j 

 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 
           i 
         j 

 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 
             i 
         j 

 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 
             i 
           j 

 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 
                 i 
           j 

 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 
                 i 
             j 

 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 
                     i 
             j 

 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 
                     i 
               j 

 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 
                         i 
               j 

 2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6 5 
                         i 
                 j 

 2 4 3 1 4 3 3 2 5 8 7 9 6 6 7 6 7 
                 ^             i   
Lewa partycja    j   Prawa partycja

Po zakończeniu podziału na partycje wskaźnik j wyznacza pozycję piwotu. Lewa partycja zawiera elementy mniejsze od piwotu i rozciąga się od początku zbioru do pozycji j - 1. Prawa partycja zawiera elementy większe lub równe piwotowi i rozciąga się od pozycji j + 1 do końca zbioru. Operacja podziału na partycje ma liniową klasę złożoności obliczeniowej - O(n).

Sortuj_szybko(lewy, prawy)

Dane wejściowe

d[ ]	- Zbiór zawierający elementy do posortowania. Zakres indeksów elementów jest dowolny.
lewy	- indeks pierwszego elementu w zbiorze, lewy C
prawy	- indeks ostatniego elementu w zbiorze, prawy C

Dane wyjściowe

Zmienne pomocnicze

piwot	-	element podziałowy
i, j	-	indeksy, i, j  C

Algorytm sortowania szybkiego wywołujemy podając za lewy indeks pierwszego elementu zbioru, a za prawy indeks elementu ostatniego (czyli Sortuj_szybko(0,n-1)). Zakres indeksów jest dowolny - dzięki temu ten sam algorytm może również sortować fragment zbioru, co wykorzystujemy przy sortowaniu wyliczonych partycji.

Na element podziałowy wybieramy element leżący w środku dzielonej partycji. Wyliczamy jego pozycję i zapamiętujemy ją tymczasowo w zmiennej i. Robimy to po to, aby dwukrotnie nie wykonywać tych samych rachunków.

Element d[i] zapamiętujemy w zmiennej piwot, a do d[i] zapisujemy ostatni element partycji. Dzięki tej operacji piwot został usunięty ze zbioru.

Ustawiamy zmienną j na początek partycji. Zmienna ta zapamiętuje pozycję podziału partycji.

W pętli sterowanej zmienną i przeglądamy kolejne elementy od pierwszego do przedostatniego (ostatni został umieszczony na pozycji piwotu, a piwot zapamiętany). Jeśli i-ty element jest mniejszy od piwotu, to trafia on na początek partycji - wymieniamy ze sobą elementy na pozycjach i-tej i j-tej. Po tej operacji przesuwamy punkt podziałowy partycji j.

Po zakończeniu pętli element z pozycji j-tej przenosimy na koniec partycji, aby zwolnić miejsce dla piwotu, po czym wstawiamy tam piwot. Zmienna j wskazuje zatem wynikową pozycję piwotu. Pierwotna partycja została podzielona na dwie partycje:

Sprawdzamy, czy partycje te obejmują więcej niż jeden element. Jeśli tak, to wywołujemy rekurencyjnie algorytm sortowania szybkiego przekazując mu granice wyznaczonych partycji. Po powrocie z wywołań rekurencyjnych partycja wyjściowa jest posortowana rosnąco. Kończymy algorytm.

1. Określamy zakres wartości, jakie mogą przyjmować elementy sortowanego zbioru. Niech w_min oznacza najmniejszą wartość, a w_max niech oznacza wartość największą.
2. Dla każdej możliwej wartości przygotowujemy kubełek-licznik, który będzie zliczał ilość wystąpień tej wartości w sortowanym zbiorze. Liczba liczników jest równa (w_max - w_min + 1). Każdy licznik jest początkowo ustawiony na wartość zero.
3. Przeglądamy kolejno elementy zbioru od pierwszego do ostatniego. Dla każdego elementu zbioru zwiększamy o jeden zawartość licznika o numerze równym wartości elementu. Na przykład, jeśli kolejny element zbioru ma wartość 3, to zwiększamy licznik o numerze 3. W efekcie po przeglądnięciu wszystkich elementów zbioru liczniki będą zawierały ilość wystąpień każdej z możliwych wartości. Jeśli dany licznik zawiera 0, to wartość równa numerowi licznika w zbiorze nie występuje. Inaczej wartość ta występuje tyle razy, ile wynosi zawartość jej licznika.
4. Przeglądamy kolejne liczniki zapisując do zbioru wynikowego ich numery tyle razy, ile wynosi ich zawartość. Zbiór wyjściowy będzie posortowany.
   

Przykład:

Dla przykładu posortujemy opisaną wyżej metodą zbiór { 2 6 4 3 8 7 2 5 7 9 3 5 2 6 }.

Najpierw określamy zakres wartości elementów (w tym celu możemy na przykład wyszukać w zbiorze element najmniejszy i największy). U nas zakres wynosi:

w_min = 2,  w_max = 9

Potrzebujemy zatem:

w_max - w_min + 1 = 9 - 2 + 1 = 8 liczników.

Liczniki ponumerujemy zgodnie z wartościami, które będą zliczały:

[2] [3] [4] [5] [6] [7] [8] [9]

Na początku sortowania wszystkie liczniki mają stan zero:

[2:0] [3:0] [4:0] [5:0] [6:0] [7:0] [8:0] [9:0]

Teraz przeglądamy kolejne elementy zbioru zliczając ich wystąpienia w odpowiednich licznikach:

{ 2 6 4 3 8 7 2 5 7 9 3 5 2 6 }

[2:3] [3:2] [4:1] [5:2] [6:2] [7:2] [8:1] [9:1]

Zapis [2:3] oznacza, iż licznik numer 2 zawiera liczbę 3, a to z kolei oznacza, iż liczba 2 pojawiła się w zbiorze 3 razy. Przeglądamy kolejne liczniki począwszy od licznika o najmniejszym numerze (w przypadku sortowania malejącego przeglądanie rozpoczynamy od licznika o największym numerze) i zapisujemy do zbioru wynikowego tyle razy numer licznika, ile wynosi jego zawartość:

[2:3] [3:2] [4:1] [5:2] [6:2] [7:2] [8:1] [9:1]

{ 2 2 2 3 3 4 5 5 6 6 7 7 8 9 }

Specyfikacja problemu

Dane wejściowe

n	- liczba elementów w zbiorze, n  N
d[ ]	- sortowany zbiór liczb całkowitych. Indeksy elementów rozpoczynają się od 0.
wmin	- minimalna wartość elementów zbioru,  wmin C
wmax	- maksymalna wartość elementów zbioru,  wmax C

Dane wyjściowe

Zmienne pomocnicze

lw[ ]	- tablica liczników wartości o indeksach od 0 do wmax - wmin. Każdy licznik przechowuje liczbę całkowitą
i, j	- zmienne licznikowe pętli, i,j C

Lista kroków

Algorytm ma klasę czasowej złożoności obliczeniowej O(m + n), gdzie m oznacza ilość możliwych wartości, które mogą przyjmować elementy zbioru, a n to ilość sortowanych elementów. Jeśli m jest małe w porównaniu z n (sortujemy dużo elementów o małym zakresie wartości), to na czas sortowania będzie miała wpływ głównie ilość elementów n i klasa złożoności uprości się do postaci O(n). Dzieje się tak dlatego, iż przy równomiernym rozkładzie dużej ilości elementów o małym zakresie wartości liczniki będą równomiernie zapełnione (stan każdego licznika będzie dążył do [ⁿ/_m]). Zatem algorytm wykona:

1. m operacji zerowania liczników - czas pomijalnie mały i przy dużym n nie wpływa istotnie na klasę algorytmu.
2. n operacji zwiększania liczników
3. n operacji przesłania numerów liczników do zbioru wynikowego - ilość pustych liczników będzie dążyła do zera.

W sytuacji odwrotnej, gdy sortujemy mało elementów o dużym zakresie wartości klasa złożoności zredukuje się z kolei do O(m) - spróbuj uzasadnić ten wynik samemu na podstawie analizy działania poszczególnych fragmentów algorytmu.

Posortować rosnąco zbiór danych:

{ 6 3 6 1 4 9 0 1 8 2 6 4 9 3 7 5 9 2 7 3 2 4 1 8 7 0 8 5 8 3 6 2 5 3 }

Czynności wstępne

Dla każdej wartości w zbiorze przygotowujemy licznik i ustawiamy go na 0.

[0:0]  [1:0]  [2:0]  [3:0]  [4:0]  [5:0]  [6:0]  [7:0] [8:0]  [9:0]

Obieg zliczający

Przeglądamy kolejne elementy zbioru i zliczamy ich wystąpienia w odpowiednich licznikach. Np. element 6 powoduje zwiększenie o 1 licznika nr 6. Po wykonaniu tego obiegu w poszczególnych licznikach mamy ilość wystąpień każdej wartości. W naszym przykładzie otrzymamy:

[0:2]  [1:3]  [2:4]  [3:5]  [4:3]  [5:3]  [6:4]  [7:3] [8:4]  [9:3]

Teraz poczynając od drugiego licznika sumujemy zawartość licznika oraz jego poprzednika i otrzymujemy:

[0:2]  [1:5]  [2:9]  [3:14]  [4:17]  [5:20]  [6:24]  [7:27] [8:31]  [9:34]

W wyniku tej operacji w każdym liczniku otrzymaliśmy ilość wartości mniejszych lub równych numerowi licznika, które występują w zbiorze wejściowym. Na przykład:

[0:2] - w zbiorze wejściowym są dwie wartości 0
[1:5] - w zbiorze wejściowym jest pięć wartości mniejszych lub równych 1
[2:9] - w zbiorze wejściowym jest dziewięć wartość mniejszych lub równych 2, itd.

Zwróć uwagę, iż stan licznika określa teraz ostatnią pozycję minus 1 w zbiorze uporządkowanym, na której należy umieścić wartość równą numerowi licznika:

Obieg dystrybucyjny

Przeglądamy jeszcze raz zbiór wejściowy idąc od ostatniego elementu do pierwszego (aby zachować stabilność sortowania). 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. Dzięki temu następna taka wartość trafi na wcześniejszą pozycję.

W naszym przykładzie rozpoczynamy od ostatniej liczby 3. Jej licznik ma zawartość [3:14]. Zatem liczbę 3 umieszczamy w zbiorze wynikowym na pozycji 14 - 1 = 13 i zmniejszamy o 1 stan licznika otrzymując [3:13]. Kolejna liczba 3 trafi teraz na pozycję 12, itd.

Dla liczby 5 stan licznika wynosi [5:20]. Umieszczamy ją zatem na 20 - 1 = 19 pozycji i licznik zmniejszamy o 1 otrzymując [5:19].

Postępujemy w ten sam sposób z pozostałymi elementami zbioru. W efekcie zbiór wynikowy będzie posortowany rosnąco:

{ 0 0 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 8 8 8 8 9 9 9 }

Podsumowanie

Przyjrzawszy się dokładnie algorytmowi sortowania przez zliczanie możesz zastanawiać się, dlaczego postępujemy w tak dziwny sposób? Przecież mając zliczone wystąpienia każdej wartości w licznikach, możemy je od razu przepisać do zbioru wyjściowego, jak zrobiliśmy w algorytmie sortowania kubełkowego. Miałbyś rację, gdyby chodziło jedynie o posortowanie liczb. Jest jednak inaczej.

Celem nie jest posortowanie jedynie samych wartości elementów. Sortowane wartości są zwykle tzw. kluczami, czyli wartościami skojarzonymi z elementami, które wyliczono na podstawie pewnego kryterium Sortując klucze chcemy posortować zawierające je elementy. Dlatego do zbioru wynikowego musimy przepisać całe elementy ze zbioru wejściowego, gdyż w praktyce klucze stanowią jedynie część (raczej małą) danych zawartych w elementach. Zatem algorytm sortowania przez zliczanie wyznacza docelowe pozycje elementów na podstawie reprezentujących je kluczy, które mogą się wielokrotnie powtarzać. Następnie elementy są umieszczane na właściwym miejscu w zbiorze wyjściowym. Prześledź dokładnie podany poniżej algorytm oraz przykładowe programy, a wszystko powinno się wyjaśnić.