Informatyka dla klas II

Opisany w tym rozdziale algorytm sortowania kubełkowego pozwala sortować zbiory liczb całkowitych - najlepiej o dużej ilości elementów, lecz o małym zakresie wartości. Zasada działania jest następująca:

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

d[ ]	- posortowany zbiór liczb całkowitych.

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

K01:	Dla i  = 0, 1,...,wmax - wmin: wykonuj lw[i] ← 0
K02:	Dla i  = 0,1,...,n - 1: wykonuj lw[ d[i] - wmin] ← lw[ d[i] - wmin] + 1
K03:	j  ← 0
K04:	Dla i  = 0 , 1,...,wmax - wmin: wykonuj K05
K05:	Dopóki lw[i] > 0 wykonuj:         d[j] ← i + wmin         lw[i] ← lw[i] - 1         j  ← j  + 1
K06:	Zakończ

 

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.

Zasadę pracy algorytmu sortowania przez zliczanie jest najlepiej przedstawić za pomocą przykładu.

 

Przykład:

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:

Wartość:	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
Pozycja:	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33

 

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ć.