Sortowanie kubełkowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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)[1]. W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n²)[potrzebne źródło].

Pomysł takiego sortowania podali po raz pierwszy w roku 1956 E. J. Issac i R. C. Singleton[2].

Sposób działania[edytuj | edytuj kod]

Idea działania algorytmu sortowania kubełkowego[1]:

  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ą[potrzebne źródło]. 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)[potrzebne źródło].

Pseudokod[edytuj | edytuj kod]

Algorytm sortowania kubełkowego wyrażony w pseudokodzie[3]:

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]

Przypisy

Bibliografia[edytuj | edytuj kod]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.
  • Samanta Debasis: Classic Data Structures 2Nd Ed.. PHI Learning Pvt. Ltd..