Wprowadzenie
Sortowanie kubełkowe (bucket sort) to algorytm wynaleziony w 1956 r. przez E.J. Issaca i R.C. Singletona, działający w czasie liniowym (O(n)). Liczby przeznaczone do tego sortowania powinny być liczbami z przedziału [0;1) i powinny być dosyć równo rozłożone w tymże przedziale. Cały algorytm opiera się na podziale przedziału [0;1) na pewną ilość równych podprzedziałów, tzw. kubełków. Następnie każda z liczb przeznaczona do sortowania jest "wrzucana" do odpowiedniego kubełka. Aby otrzymać posortowane liczby najpierw sortuje się liczby w każdym z kubełków, a następnie łączy się je wszystkie po kolei.
Przykład
W przykładzie poniżej przedstawiłem sortowanie kubełkowe dla 10 kubełków. Kubełki są ponumerowane od 0 do 9. Każda liczba trafia do kubełka takiego, jaką ma pierwszą cyfrę po przecinku. Oto liczby przeznaczone do posortowania:
| 0,78 | 0,15 | 0,26 | 0,02 | 0,64 | 0,76 | 0,63 | 0,59 | 0,25 | 0,74 | 0,15 | 0,18 | 0,82 | 0,79 | 0,39 |
Teraz każdą z liczb należy wrzucić do odpowiedniego kubełka. Jak to jest napisane powyżej zależy to od pierwszej liczby po przecinku danej liczby. Poniżej przedstawiam liczby wraz z numer kubełka do którego trafią:
| Liczba | 0,78 | 0,15 | 0,26 | 0,02 | 0,64 | 0,76 | 0,63 | 0,59 | 0,25 | 0,74 | 0,15 | 0,18 | 0,82 | 0,79 | 0,39 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Numer kubełka: | 7 | 1 | 2 | 0 | 6 | 7 | 6 | 5 | 2 | 7 | 1 | 1 | 8 | 7 | 3 |
Oto kubełki wraz z liczbami, które zostały po kolei do nich wrzucone:
| Kubełek | Liczby |
|---|---|
| 0 | 0,02 |
| 1 | 0,15; 0,15; 0,18 |
| 2 | 0,26; 0,25 |
| 3 | 0,39 |
| 4 | |
| 5 | 0,59 |
| 6 | 0,64; 0,63; |
| 7 | 0,78; 0,76; 0,74; 0,79 |
| 8 | 0,82 |
| 9 |
Liczby zostały już przydzielone do odpowiednich kubełków. Teraz należy je posortować w każdym z nich. Po sortowaniu otrzymujemy:
| Kubełek | Liczby |
|---|---|
| 0 | 0,02 |
| 1 | 0,15; 0,15; 0,18 |
| 2 | 0,25; 0,26 |
| 3 | 0,39 |
| 4 | |
| 5 | 0,59 |
| 6 | 0,63; 0,64; |
| 7 | 0,74; 0,76; 0,78; 0,79 |
| 8 | 0,82 |
| 9 |
Teraz wystarczy po kolei połączyć zawartość wszystkich kubełków i liczby będą już posortowane. W naszym przypadku wygląda to następująco:
| 0,02 | 0,15 | 0,15 | 0,18 | 0,25 | 0,26 | 0,39 | 0,59 | 0,63 | 0,64 | 0,74 | 0,76 | 0,78 | 0,79 | 0,82 |
I w ten sposób doszliśmy do końca algorytmu sortowania kubełkowego.
Na koniec parę uwag. Do reprezentacji kubełków najlepiej jest użyć struktur danych zwanych listami. Jako algorytmu do sortowania kubełków można użyć sortowania przez wstawianie. Mimo, że ma on złożoność O(n2) to ogólnie sortowanie kubełkowe ma złożoność O(n). Wynika to z tego, że dane wejściowe są równomiernie rozłożone w przedziale [0;1).
W przypadku, gdy mamy do posortowania liczby spoza przedziału [0;1) to należy każdą z nich podzielić przez sumę największej liczby w danych ciągu i liczby 1. W ten sposób wszystkie liczby będą w zadanym przedziale. Należy dodać w tym przypadku dodać 1 do największej liczby, bo gdy będziemy dzielić właśnie ją to otrzymamy liczbę 1, a ta liczba do przedziału podanego wyżej nie należy.