Sortowanie kubełkowe
Z Wikipedii
Sortowanie kubełkowe (ang. bucket sort) to 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.
[edytuj] Sposób działania
- Podziel zadany przedział liczb na n 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).
[edytuj] Literatura
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, "Wprowadzenie do algorytmów", WNT 2001
