Sortowanie kubełkowe – algorytm i implementacje w C++, Javie i Python
Nadszedł kolejny piątek, a wraz z nim kolejna część „Piątku z sortowaniem”. Czy jesteście gotowi na poznanie nowego algorytmu? Dziś pod lupę weźmiemy sortowanie kubełkowe (bucket sort). Bierzmy się do roboty.
Działanie
Algorytm sortowania kubełkowego jest znacznie przystępniejszy, od omawianego w poprzednim tekście sortowania binarnego. Jest on szczególnie przyjazny, w przypadku sortowania liczb całkowitych. Jak zwykle, wytłumaczmy na początku, w jaki sposób funkcjonuje ten algorytm.
Jego działanie, dzielimy na kilka prostych kroków. W pierwszym z nich, określamy dwa indeksy ymin i ymax, które mówią nam o najmniejszej i największej wartości, występującej w zbiorze. Wartości te przydadzą nam się głównie w implementacji tego algorytmu. Następnie przygotowujemy „kubełki” zliczające ilość wystąpień danych wartości w zborze. Ilość „kubełków”, możemy obliczyć ze wzoru ymin – ymax +1.
W kolejnym z kroków zliczamy liczbę wystąpień poszczególnych elementów, zwiększając wartość „kubełka” o indeksie, który odpowiada indeksowi rozpatrywanego elementu. Np. gdy natkniemy się na element o wartości 5, zwiększamy wartość „kubełeka” o indeksie 5.
W ostatnim kroku, tworzymy nowy zbiór. By tego dokonać, przechodzimy przez wszystkie liczniki, dodając do zbioru tyle poszczególnych elementów, ile ma wartość odpowiadającego mu kubełka. W ten właśnie prosty sposób otrzymamy posortowany zbiór wejściowy.
Przykład – liczby całkowite
Nic lepiej nie pomoże zrozumieć algorytmu, jak prosty przykład. Weźmy zbiór { 1, 5, 1, 5, 1, 2, 4, 5 }. W pierwszym kroku wyznaczmy ymin i ymax. Wynoszą one w tym przypadku 1 oraz 5. Tworzymy więc 5 „kubełków”:
B1 = 0, B2 = 0, B3 = 0, B4 = 0, B5 = 0
W kolejnym kroku liczymy ilość wystąpień poszczególnych
elementów, zapisując je w kubełkach:
B1 = 3, B2 = 1, B3 =
0, B4 = 1, B5 = 3
Kończymy zapisując do nowego zbioru daną ilość elementów o wartościach indeksów kubełków. W ten sposób otrzymujemy: { 1,1,1,2,4,5,5,5 }. Zbiór ten odpowiada posortowanemu zbiorowi wejściowemu. By dodatkowo ułatwić zrozumienie tego procesu, spójrzcie na poniższą animację:
cout<<endl<<"Oto tablica po sortowaniu:"<<endl;
printTab(tab,n);
delete[] tab;
delete[] minAndMax;
system("pause");
return0;
}
voidprintTab(int*tab,intn){
cout<<endl<<"\t| ";
for(intx=0;x<n;x++){
cout<<tab[x] << " | ";
}
cout<<endl<<endl;
}
//Funkcja do wyszukiwania największej i
//najmniejszej wartości w tablicy
int*findMinAndMax(int*tab,intn)
{
int*minAndMax=newint[2];
minAndMax[0] = tab[0];
minAndMax[1] = tab[0];
for(intx=0;x<n;x++)
{
if(tab[x] < minAndMax[0])
{
minAndMax[0] = tab[x];
}
if(tab[x] > minAndMax[1])
{
minAndMax[1] = tab[x];
}
}
returnminAndMax;
}
Java
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
packagematura;
import java.util.Scanner;
publicclassMain{
privatestaticvoidprintArray(int[] tab) {
System.out.println();
for(inti=0;i<tab.length;i++)
{
System.out.print(tab[i] + " | ");
}
System.out.println();
}
privatestaticint[] getMinMax(int[] arr) {
int[] result = new int[2];
result[0] = arr[0]; // pierwszy element bedzie najmniejszym elementem
result[1] = arr[0]; // drugi element bedzie najwiekszym elementem
for(inti:arr){
if(result[0] > i) { //dokonujemy podmiany najwiekszego/najmniejszego elementu w przypadku gdy iterowana wartosc bedzie wieksza/mniejsza od przechowanej
result[0] = i;
}
elseif(result[1] < i) {
result[1] = i;
}
}
returnresult;
}
privatestaticvoidbucketSort(int[] tab) {
int[] results = getMinMax(tab);
intyMax=results[1];
intyMin=results[0];
int[] buckets = new int[yMax - yMin + 1];
//Wstawiamy początkowe wartości liczników
for(intx=0;x<(yMax-yMin+1);x++)
{
buckets[x] = 0;
}
System.out.println("Stworzono kubelki: ");
for(intx=0;x<(yMax-yMin+1);x++){
System.out.print("B"+(x+yMin)+" | ");
}
System.out.println();
for(intx=0;x<tab.length;x++)
{
//Zliczamy ilość wystąpień poszczególnych elementów
buckets[tab[x]-yMin] += 1 #zliczamy nastepnie ilosc wystapien dla kazdego z kubelkow
print("Zliczono elementy:")
forxinrange(yMax-yMin+1):
print("B",(x+yMin),"=",buckets[x], end=" | ")
print()
lastIndex=0
forxinrange(yMax-yMin+1):#na koniec sortujemy podlug kubelkow tablice
y=lastIndex
whiley<buckets[x] + lastIndex:
tab[y] = x+yMin
y+=1
lastIndex=y
print("Podaj ilosc elementow tablicy:")
a=int(input())
tablica=[]
foriinrange(a):
print("Podaj element nr. ",(i+1))
tablica.append(int(input()))
print("Oto twoja tablica:")
wypisz(tablica)
sortujKub(tablica,a)
print("Oto twoja tablica po sortowaniu:")
wypisz(tablica)
Przykład – liczby ułamkowe
Sortowanie kubełkowe nie służy jednak tylko i wyłącznie do sortowania liczb całkowitych. Można nim sortować także liczby typu float. Tu sprawa robi się jednak nieco bardziej skomplikowana. Podobnie jak w przypadku liczb całkowitych, tworzyć będziemy „kubełki”. Tym razem, nie będą one jedynie licznikami, a będą strukurami przechowującymi wartości w wyznaczonych zakresach. Przykładowo, kubełek o indeksie 0, będzie przechowywał liczby w zakresie [0, 1). Nie wystarczy nam więc jedynie dodać liczby do kubełków. W końcowym kroku należy posortować poszczególne kubełki, przy pomocy innego algorytmu sortowania np. sortowaniem przez wstawianie, który również omawialiśmy w „Piątku z sortowaniem”.
Poszczególne kroki będą więc wyglądać w następujący sposób:
Wyznaczamy ymin i ymax
Tworzymy kubełki będące podzakresami
Dodajemy poszczególne elementy zbioru do
kubełków
Sortujemy wszystkie kubełki
Zapisujemy po kolei elementy ze wszystkich
kubełków
Przykład – ułamki
Weźmy zbiór {0.48, 0.27, 0.12, 0.21, 0.43, 0.25}. W pierwszej kolejności wyznaczymy ymin i ymax, wynoszące 0.12 i 0.48, a następnie stwórzmy kubełki:
B1 = {}, B2 = {}, B3
= {}, B4 = {}
Kolejno umieszczamy każdy z elementów w kubełku, którego
zakres odpowiada wartości danego elementu:
result[0] = arr[0]; // pierwszy element bedzie najmniejszym elementem
result[1] = arr[0]; // drugi element bedzie najwiekszym elementem
for(floati:arr){
if(result[0] > i) { //dokonujemy podmiany najwiekszego/najmniejszego elementu w przypadku gdy iterowana wartosc bedzie wieksza/mniejsza od przechowanej
forxinrange(bucketsAmount):#po czym mozemy przystapic do wstawiania ich w wyjsciowa tablice
z=0
foryinrange(len(buckets[x])):
tab[y+lastIndex] = buckets[x][y]
z+=1
lastIndex+=z
print("Podaj ilosc elementow tablicy:")
a=int(input())
tablica=[]
foriinrange(a):
print("Podaj element nr. ",(i+1))
tablica.append(float(input()))
print("Oto twoja tablica:")
wypisz(tablica)
sortujKub(tablica,a)
print("Oto twoja tablica po sortowaniu:")
wypisz(tablica)
Trochę teorii
Jest to niezwykle ciekawy algorytm, ze względu na swoją efektywność. Sortowanie kubełkowe, radzi sobie najlepiej ze zbiorami o dużej ilości elementów, lecz małym zakresie wartości. W przypadku zbioru stosunkowo małym zakresie, i dużej ilości elementów, algorytm ten będzie niezwykle efektywny, dążąc do optymistycznej złożoności O(n).
Niestety w pesymistycznym przypadku, ma on złożoność rzędu O(n2), czyli taką jak chociażby niesławne sortowanie bąbelkowe, którego opis znajdziecie tutaj.
Podsumowanie
Za nami kolejny algorytm sortowania, tym razem z dwoma implementacjami. Za tydzień spotykamy się ponownie, by poznać następny! Zapraszamy Was również na naszą facebookową grupę, na której znajdziecie materiały pomocnicze do matury z informatyki, dotyczące nie tylko algorytmów.
Cześć! Jestem uczniem liceum i akurat szukałem algorytmów sortujących ucząc się do matury. Trafiłem na twoją stronę. Przeczytałem artykuł, zrozumiałem algorytm, napisałem program, a następnie zdziwiłem się o ile jest krótszy od Twojego przykładowego. Czy to ja popełniłem gdzieś błąd? A może Ty napisałeś go specjalnie troszkę rozwleklej aby każdy go zrozumiał? Pozdrawiam!
Poniżej wklejam moje rozwiązanie problemu w Pythonie
from random import randrange as rr
from pprint import pprint as pp
tab = [rr(7) for i in range(20)]
print(tab)
def sortowanie_kubelkowe(tab):
dict = {letter: tab.count(letter) for letter in set(tab)}
tab.clear()
for value, number_of_appearance in dict.items():
for i in range(number_of_appearance):
tab.append(value)
return tab ,dict
Pominięto chyba najważniejsze zastosowanie sortowania kubełkowego – porządkowanie ciągów znaków, słów nad jakimś alfabetem i to dowolnej i różnej długości. Szczegóły w M.M.Sysło, Algorytmy, Helion 2016.
mike_Y
says:Cześć! Jestem uczniem liceum i akurat szukałem algorytmów sortujących ucząc się do matury. Trafiłem na twoją stronę. Przeczytałem artykuł, zrozumiałem algorytm, napisałem program, a następnie zdziwiłem się o ile jest krótszy od Twojego przykładowego. Czy to ja popełniłem gdzieś błąd? A może Ty napisałeś go specjalnie troszkę rozwleklej aby każdy go zrozumiał? Pozdrawiam!
Poniżej wklejam moje rozwiązanie problemu w Pythonie
from random import randrange as rr
from pprint import pprint as pp
tab = [rr(7) for i in range(20)]
print(tab)
def sortowanie_kubelkowe(tab):
dict = {letter: tab.count(letter) for letter in set(tab)}
tab.clear()
for value, number_of_appearance in dict.items():
for i in range(number_of_appearance):
tab.append(value)
return tab ,dict
print(sortowanie_kubelkowe(tab))
msy
says:Pominięto chyba najważniejsze zastosowanie sortowania kubełkowego – porządkowanie ciągów znaków, słów nad jakimś alfabetem i to dowolnej i różnej długości. Szczegóły w M.M.Sysło, Algorytmy, Helion 2016.