Sortowanie kubełkowe (ang. bucket sort) – jeden z algorytmów sortowania, najczęściej stosowany, gdy liczby w zadanym przedziale są rozłożone jednostajnie, ma on wówczas złożoność Θ(n). W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n²).
Pomysł takiego sortowania podali po raz pierwszy w roku 1956 E. J. Issac i R. C. Singleton.
Sposób działania Idea działania algorytmu sortowania kubełkowego: Podziel zadany przedział liczb na k podprzedziałów (kubełków) o równej długości. Przypisz liczby z sortowanej tablicy do odpowiednich kubełków. Sortuj liczby w niepustych kubełkach. Wypisz po kolei zawartość niepustych kubełków.
Zazwyczaj przyjmuje się, że sortowane liczby należą do przedziału od 0 do 1 - jeśli tak nie jest, to można podzielić każdą z nich przez największą możliwą (jeśli znany jest przedział) lub wyznaczoną. Należy tu jednak zwrócić uwagę, że wyznaczanie największej możliwej liczby w tablicy m-elementowej ma złożoność obliczeniową O(m).
Pseudokod Algorytm sortowania kubełkowego wyrażony w pseudokodzie:
function bucket-sort(array, n) is buckets ← new array of n empty lists for i = 0 to (length(array)-1) do insert array[i] into buckets[msbits(array[i], k)] for i = 0 to n – 1 do next-sort(buckets[i]) return the concatenation of buckets, ..., buckets[n-1]
Przypisy
Bibliografia
Kubełkowe