Sortowanie kubełkowe ( ang . bucket sort) – jeden z algorytmów sortowania . Jest on 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

1. Podziel zadany przedział liczb na n podprzedziałów (kubełków) o równej długości.
2. Przypisz liczby z sortowanej tablicy do odpowiednich kubełków.
3. Sortuj liczby w niepustych kubełkach.
4. 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

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[0], ..., buckets[n-1]

Literatura

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, "Wprowadzenie do algorytmów", WNT 2001