Przeczytaj

Sortowanie kubełkowekubełekkubełkowe należy do algorytmów, które porządkują dane w czasie liniowym. Sortowane dane powinny być liczbami całkowitymi, może być ich wiele, jednak ich zakres nie powinien być zbyt duży.

Zasada działania algorytmu – liczby całkowite

Jak sama nazwa wskazuje, w algorytmie posługujemy się kubełkami. Pracę rozpoczynamy od ustalenia, ilu ich potrzebujemy. W tym celu wyszukujemy w sortowanej tablicy największą oraz najmniejszą wartość. Oznaczamy je jako $x_{m i n}$ oraz $x_{m a x}$ . Wartości te definiują liczbę kubełków $k$ . Potrzebujemy osobnego kubełka dla każdej liczby całkowitej w przedziale $[x_{m i n}; x_{m a x}]$ , co opisane jest wzorem:

k = x_{max} - x_{min} + 1

Atrybutem każdego kubełka jest indeks odpowiadający konkretnej liczbie z sortowanej tablicy. Rozpoczynamy od pierwszego kubełka, nadając mu indeks $x_{m i n}$ , a kończymy na ostatnim, któremu przydzielimy indeks $x_{m a x}$ .

Przyjmujemy, że każdy kubełek początkowo przechowuje liczbę 0, jednak docelowo wartość ta ma przedstawiać liczbę wystąpień danego składnika sortowanej tablicy. Po kolei odczytujemy liczbę powtórzeń poszczególnych elementów i aktualizujemy liczbę elementów umieszczonych w kubełkach.

Ostatnim krokiem jest zapełnianie tablicy wynikowej. Wpisujemy indeksy kolejnych kubełków do tablicy tyle razy, ile wynosi wartość danego kubełka. Rozpoczynamy od indeksu $x_{m i n}$ , a kończymy na $x_{m a x}$ . W rezultacie tej operacji otrzymujemy posortowaną tablicę.

Przykład 1

Używając algorytmu sortowania kubełkowego, posortujemy niemalejąco zbiór ${1, 0, 1, 7, 5, 4, 4}$ . Wartości $x_{m i n}$ oraz $x_{m a x}$ prezentują się następująco:

x_{min} = 0

x_{max} = 7

Obliczamy, ilu kubełków potrzebujemy.

k = 7 - 0 + 1 = 8

Jako oznaczenie kubełków przyjmiemy $a_{x}$ . Wartość każdego z nich początkowo równa jest 0.

a_{0} = 0, a_{1} = 0, a_{2} = 0, a_{3} = 0, a_{4} = 0, a_{5} = 0, a_{6} = 0, a_{7} = 0

Ustalamy liczbę wystąpień kolejnych składników zbioru.

Liczba 0 występuje jeden raz, zatem kubełek $a_{0}$ przyjmuje wartość 1.

Liczba 1 występuje dwa razy, zatem kubełek $a_{1}$ przyjmuje wartość 2.

Liczba 2 nie występuje ani razu, zatem kubełek $a_{2}$ przyjmuje wartość 0 itd.

W konsekwencji otrzymujemy następujące kubełki:

a_{0} = 1, a_{1} = 2, a_{2} = 0, a_{3} = 0, a_{4} = 2, a_{5} = 1, a_{6} = 0, a_{7} = 1

Możemy teraz posortować liczby na podstawie wartości kubełków, rozpoczynając od $a_{0}$ . Wartości z kubełków oznaczają, ile razy ma wystąpić liczba podana jako indeks kubełka. Wpisujemy do wynikowej tablicy odpowiednio jedną liczbę 0, dwie liczby 1 itd. Dopiero z niej wypisujemy posortowany zbiór:

{0, 1, 1, 4, 4, 5, 7}

Przykład 2

Wróćmy do kwestii dużej różnicy między maksymalną i minimalną wartością sortowanego zbioru. Załóżmy, że do posortowania mamy następujący zbiór: ${1, 0, 1, 7, 5, 4, 104}$ . Wartości $x_{m i n}$ oraz $x_{m a x}$ prezentują się następująco:

$x_{\min}=0$

$x_{\max}=104$

Ustalamy, ilu kubełków potrzebujemy:

$k=104-0+1=105$

Pomimo że mamy do posortowania tyle samo elementów co w przykładzie 1, znacząco zwiększa się liczba kubełków, które należy utworzyć. Co powoduje, że zajmujemy więcej zasobów obliczeniowych komputera.

Ważne!

Nie zawsze w danym kubełku przechowujemy jedną liczbę. Istnieje możliwość stworzenia kubełków zawierających elementy tablicy z wybranych przedziałów (wszystkie przedziały muszą być tej samej długości). Wówczas wewnątrz każdego z kubełków należy wykonać osobno proces sortowania. Można do tego użyć dowolnego algorytmu sortującego. W ostatnim kroku wpisujemy po kolei posortowane wartości z kubełków do tablicy.

Pseudokod

Zapiszmy algorytm sortowania kubełkowego dla liczb całkowitych za pomocą pseudokodu.

Specyfikacja problemu:

Dane:

n – liczba elementów w tablicy tab do posortowania
tab[0..n‑1] – tablica liczb całkowitych zawierająca dane do posortowania

Wynik:

tab[0..n‑1] – tablica liczb całkowitych posortowana niemalejąco

Ustalmy teraz liczbę kubełków potrzebnych do wykonania algorytmu. Skorzystamy z przywoływanego już wzoru, a wynik zapiszemy w zmiennej k. Wymagane do tego będzie wskazanie wartości minimalnej oraz maksymalnej, które znajdują się w tablicy tab.

xmin ← tab[0]
xmax ← tab[0]

dla i = 1, 2, ..., n - 1 wykonuj:
	jeżeli tab[i] < xmin:
		xmin ← tab[i]
	jeżeli tab[i] > xmax
		xmax ← tab[i]

k ← xmax - xmin + 1

Następnie tworzymy kubełki i przypisujemy im domyślną wartość 0.

kubelki[0..k - 1]
dla i = 0, 1, ..., k - 1 wykonuj:
	kubelki[i] ← 0

Zliczamy, ile razy dana wartość występuje w wejściowej tablicy tab. Ustalamy, w którym kubełku należy zapisać informację o liczbie wystąpień danej liczby. Odejmiemy od każdej rozpatrywanej liczby wartość zmiennej xmin, co spowoduje zapisanie liczby wystąpień najmniejszej liczby w tablicy w kubełku o indeksie 0, drugiej najmniejszej do kubełka o indeksie 1 itd. Dla każdej liczby dokonujemy inkrementacji wartości znajdującej się w przypisanym do niej kubełku.

dla i = 0, 1, ..., n - 1 wykonuj:
	kubelki[tab[i] - xmin] ← kubelki[tab[i] - xmin] + 1

Wypełniamy tablicę posortowanymi liczbami. Odczytujemy, ile razy wystąpił dany element, a następnie tyle razy wypisujemy go do wynikowej tablicy.

indeks_tab ← 0
indeks_kubelka ← 0

dopóki indeks_tab < n wykonuj:
	jeżeli kubelki[indeks_kubelka] != 0:
		# kubełek niepusty, zapisz zliczoną wartość do tablicy wynikowej
		tab[indeks_tab] = xmin + indeks_kubelka

        # zmniejsz o 1 liczbę wystąpień wartości
		kubelki[indeks_kubelka] ← kubelki[indeks_kubelka] - 1

        # przejdź do następnej komórki
		indeks_tab ← indeks_tab + 1

	w przeciwnym razie:
		# kubełek pusty, przejdź do następnego kubełka
		indeks_kubelka ← indeks_kubelka + 1

Implementacja algorytmu sortowania kubełkowego zapisana za pomocą pseudokodu prezentuje się następująco:

Linia 1. xmin ← tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 2. xmax ← tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 4. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek n minus 1 wykonuj dwukropek. Linia 5. jeżeli tab otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny xmin dwukropek. Linia 6. xmin ← tab otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 7. jeżeli tab otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny xmax. Linia 8. xmax ← tab otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 10. k ← xmax minus xmin plus 1. Linia 11. kubelki otwórz nawias kwadratowy 0 kropka kropka k minus 1 zamknij nawias kwadratowy. Linia 12. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek k minus 1 wykonuj dwukropek. Linia 13. kubelki otwórz nawias kwadratowy i zamknij nawias kwadratowy ← 0. Linia 15. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj dwukropek. Linia 16. kubelki otwórz nawias kwadratowy tab otwórz nawias kwadratowy i zamknij nawias kwadratowy minus xmin zamknij nawias kwadratowy ← kubelki otwórz nawias kwadratowy tab otwórz nawias kwadratowy i zamknij nawias kwadratowy minus xmin zamknij nawias kwadratowy plus 1. Linia 18. indeks podkreślnik tab ← 0. Linia 19. indeks podkreślnik kubelka ← 0. Linia 21. dopóki indeks podkreślnik tab otwórz nawias ostrokątny n wykonuj dwukropek. Linia 22. jeżeli kubelki otwórz nawias kwadratowy indeks podkreślnik kubelka zamknij nawias kwadratowy wykrzyknik znak równości 0 dwukropek. Linia 23. kratka kubełek niepusty przecinek zapisz zliczoną wartość do tablicy wynikowej. Linia 24. tab otwórz nawias kwadratowy indeks podkreślnik tab zamknij nawias kwadratowy znak równości xmin plus indeks podkreślnik kubelka. Linia 26. kratka zmniejsz o 1 liczbę wystąpień wartości. Linia 27. kubelki otwórz nawias kwadratowy indeks podkreślnik kubelka zamknij nawias kwadratowy ← kubelki otwórz nawias kwadratowy indeks podkreślnik kubelka zamknij nawias kwadratowy minus 1. Linia 29. kratka przejdź do następnej komórki. Linia 30. indeks podkreślnik tab ← indeks podkreślnik tab plus 1. Linia 32. w przeciwnym razie dwukropek. Linia 33. kratka kubełek pusty przecinek przejdź do następnego kubełka. Linia 34. indeks podkreślnik kubelka ← indeks podkreślnik kubelka plus 1.

xmin ← tab[0]
xmax ← tab[0]

dla i = 1, 2, ..., n - 1 wykonuj:
	jeżeli tab[i] < xmin:
		xmin ← tab[i]
	jeżeli tab[i] > xmax
		xmax ← tab[i]

k ← xmax - xmin + 1
kubelki[0..k - 1]
dla i = 0, 1, ..., k - 1 wykonuj:
	kubelki[i] ← 0

dla i = 0, 1, ..., n - 1 wykonuj:
	kubelki[tab[i] - xmin] ← kubelki[tab[i] - xmin] + 1

indeks_tab ← 0
indeks_kubelka ← 0

dopóki indeks_tab < n wykonuj:
	jeżeli kubelki[indeks_kubelka] != 0:
		# kubełek niepusty, zapisz zliczoną wartość do tablicy wynikowej
		tab[indeks_tab] = xmin + indeks_kubelka

        # zmniejsz o 1 liczbę wystąpień wartości
		kubelki[indeks_kubelka] ← kubelki[indeks_kubelka] - 1

        # przejdź do następnej komórki
		indeks_tab ← indeks_tab + 1

	w przeciwnym razie:
		# kubełek pusty, przejdź do następnego kubełka
		indeks_kubelka ← indeks_kubelka + 1

Złożoność czasowa algorytmu

Ważną cechą każdego algorytmu jest jego złożoność czasowazłożoność czasowazłożoność czasowa, która pozwala porównywać między sobą różne metody obliczeniowe. Aby ją oszacować, nie mierzy się czasu wykonywania algorytmu, który zależny jest od implementacji i sprzętu, lecz wyróżnia się jakąś operację dominującą. Liczba wykonanych operacji dominujących zależy od rozmiaru wejścia, można więc powiedzieć, że złożoność czasowa to pewna funkcja danych wejściowych. Rząd wielkości tej funkcji wyrażającej liczbę operacji dominujących zapisuje się za pomocą notacji dużego O.

W przypadku przedstawionego wcześniej algorytmu sortowania kubełkowego rozmiarem wejścia będzie liczba elementów w tablicy wejściowej, którą oznaczymy jako $n$ , oraz liczba kubełków – $k$ .

Operacje dominujące w przedstawionym algorytmie:

Podczas wyszukiwania elementu minimalnego i maksymalnego operacją dominującą jest porównanie, trzeba wykonać $2 \cdot n - 2$ operacji.
Podczas przygotowywania kubełków operacją dominującą jest przypisanie, trzeba wykonać $k$ takich operacji.
Podobnie zliczenie wystąpień również wymaga $n$ operacji przypisania.
Przepisanie liczb do tablicy wynikowej wymaga sprawdzenia (operacja porównania) $k$ kubełków i wykonania $n$ przypisań, daje to: $n + k$ operacji.

Funkcję wyrażającą liczbę operacji dominujących możemy więc zapisać jako $f(n) = 4 \cdot n + 2 \cdot k - 2$ . Ponieważ przy zapisie oszacowania pomijamy stałe, ostatecznie mamy do czynienia ze złożonością liniową $O(n + k)$ .

Jeżeli elementów będzie dużo, ale o małym zakresie wartości ( $n$ znacznie większe niż $k$ ), to algorytm będzie działał w czasie liniowym ze względu na liczbę elementów w tablicy tab: $O(n)$ .

Natomiast w przypadku odwrotnym, czyli gdy będzie do posortowania mało elementów, ale z dużego zakresu wartości, algorytm będzie działał w czasie liniowym ze względu na zakres wartości: $O(k) = O(x_{max} - x_{min} + 1)$ .

Zasada działania algorytmu – liczby rzeczywiste

Polecenie 1

Zapoznaj się z algorytmem sortowania kubełkowego liczb rzeczywistych z przedziału $< 0; 1)$ . Przeanalizuj kolejne jego kroki, a następnie zastanów się nad różnicami pomiędzy sortowaniem liczb całkowitych i zmiennoprzecinkowych.

RjJnK9VqoNpNQ1

Pseudokod

Zapiszmy algorytm sortowania kubełkowego dla liczb rzeczywistych za pomocą pseudokodu.

Specyfikacja problemu:

Dane:

n – liczba elementów w tablicy tab do posortowania
tab[0..n‑1] – tablica liczb rzeczywistych z przedziału $\langle 0; 1 )$ zawierająca dane do posortowania

Wynik:

tab[0..n‑1] – tablica liczb rzeczywistych posortowana niemalejąco

Przyjmujemy także, że kubełków jest 10. Każdy z nich będzie listą (tablicą z możliwością dowolnego jej rozszerzania) i zawierał będzie liczby z przedziału $\langle x; x+0{,}1 )$ dla $x = 0; 0{,}1; ...; 0{,}9$ . Tworzymy zatem te kubełki.

kubelki[0..9]
dla i = 0, 1, ..., 9 wykonuj:
	kubelki[i] ← nowa, pusta lista

Następnie każdą liczbę z sortowanej tablicy tab umieszczamy w odpowiadającym jej kubełku.

dla i = 0, 1, ..., n - 1 wykonuj:
	indeks ← tab[i] * 10
	zaokrąglij w dół zawartość zmiennej indeks
	dodaj tab[i] do kubełka kubelki[indeks]

Jako algorytm pomocniczy implementujemy sortowanie bąbelkowePCfvfjgLksortowanie bąbelkowe.

funkcja sortowanieBabelkowe(tab)
	n ← długość(tab)
	dla i = 0, 1, ..., n - 1 wykonuj:
		dla j = 1, 2, ..., n - 1 - i wykonuj:
			jeżeli tab[j - 1] > tab[j]:
				zamień tab[j - 1] z tab[j]

Wykorzystując sortowanie bąbelkowe, sortujemy każdy kubełek osobno.

dla i = 0, 1, ..., 9 wykonuj:
	sortowanieBabelkowe(kubelki[i])

Na koniec przepisujemy liczby z kolejnych kubełków do tablicy wynikowej.

j ← 0
dla i = 0, 1, ..., 9 wykonuj:
	dla k = 0, 1, ..., długość(kubelki[i]) - 1 wykonuj:
		tab[j] ← kubelki[i][k]
		j ← j + 1

Cały algorytm zapisany za pomocą pseudokodu prezentuje się następująco:

Linia 1. funkcja sortowanieBabelkowe otwórz nawias okrągły tab zamknij nawias okrągły. Linia 2. n ← długość otwórz nawias okrągły tab zamknij nawias okrągły. Linia 3. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj dwukropek. Linia 4. dla j znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek n minus 1 minus i wykonuj dwukropek. Linia 5. jeżeli tab otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy zamknij nawias ostrokątny tab otwórz nawias kwadratowy j zamknij nawias kwadratowy dwukropek. Linia 6. zamień tab otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy z tab otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 8. kubelki otwórz nawias kwadratowy 0 kropka kropka 9 zamknij nawias kwadratowy. Linia 9. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 9 wykonuj dwukropek. Linia 10. kubelki otwórz nawias kwadratowy i zamknij nawias kwadratowy ← nowa przecinek pusta lista. Linia 12. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj dwukropek. Linia 13. indeks ← tab otwórz nawias kwadratowy i zamknij nawias kwadratowy asterysk 10. Linia 14. zaokrąglij w dół zawartość zmiennej indeks. Linia 15. dodaj tab otwórz nawias kwadratowy i zamknij nawias kwadratowy do kubełka kubelki otwórz nawias kwadratowy indeks zamknij nawias kwadratowy. Linia 17. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 9 wykonuj dwukropek. Linia 18. sortowanieBabelkowe otwórz nawias okrągły kubelki otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 20. j ← 0. Linia 21. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 9 wykonuj dwukropek. Linia 22. dla k znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek długość otwórz nawias okrągły kubelki otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły minus 1 wykonuj dwukropek. Linia 23. tab otwórz nawias kwadratowy j zamknij nawias kwadratowy ← kubelki otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy k zamknij nawias kwadratowy. Linia 24. j ← j plus 1.

funkcja sortowanieBabelkowe(tab)
	n ← długość(tab)
	dla i = 0, 1, ..., n - 1 wykonuj:
		dla j = 1, 2, ..., n - 1 - i wykonuj:
			jeżeli tab[j - 1] > tab[j]:
				zamień tab[j - 1] z tab[j]

kubelki[0..9]
dla i = 0, 1, ..., 9 wykonuj:
	kubelki[i] ← nowa, pusta lista

dla i = 0, 1, ..., n - 1 wykonuj:
	indeks ← tab[i] * 10
	zaokrąglij w dół zawartość zmiennej indeks
	dodaj tab[i] do kubełka kubelki[indeks]

dla i = 0, 1, ..., 9 wykonuj:
	sortowanieBabelkowe(kubelki[i])

j ← 0
dla i = 0, 1, ..., 9 wykonuj:
	dla k = 0, 1, ..., długość(kubelki[i]) - 1 wykonuj:
		tab[j] ← kubelki[i][k]
		j ← j + 1

Słownik

kubełek

podprzedział wyodrębniony z sortowanego zbioru danych

sortowanie

czynność polegająca na uporządkowaniu danych w zbiorze względem danego kryterium

złożoność czasowa

ilość czasu potrzebnego do wykonania zadania, wyrażona jako funkcja ilości danych

złożoność obliczeniowa

ilość zasobów komputerowych potrzebnych do wykonania zadania

Wprowadzenie

Schemat interaktywny

Zasada działania algorytmu – liczby całkowite

Pseudokod

Złożoność czasowa algorytmu

Zasada działania algorytmu – liczby rzeczywiste

Pseudokod

Słownik