Sortowanie kubełkowe.
W procedurze BUCKET-SORT korzystamy z pomocniczej tablicy
W algorytmie sortowanie kubełkowe zakładamy, że dana jest
list (kubełków) B[0..n - 1].
n-elementowa tablica wejściowa A, której elementy są liczbami
rzeczywistymi z przedziału [0, 1).
BUCKET-SORT(A, n)
Sortowanie kubełkowe polega na podziale przedziału [0, 1) na n
1. begin
podprzedziałów jednakowych rozmiarów, tzw. kubełków, a
2. for i := 1 to n do
następnie  rozrzuceniu liczb wejściowych do kubełków, do których
3. wstaw A[i] na listÄ™ B[ nA[i] ];
należą. Aby otrzymać ciąg wynikowy, sortujemy najpierw liczby w
4. for i := 0 to n - 1 do
każdym kubełku, a następnie wypisujemy je, przeglądając po kolei
5. posortuj listÄ™ B[i] przez wstawianie;
kubełki.
6. połącz listy B[0], B[1], . . . , B[n - 1] z zachowaniem kolejności;
7. end;
Zauważmy, że jeśli liczby wejściowe są rozłożone jednostajnie w
przedziale [1, 0), to możemy oczekiwać, że w każdym z kubełków
będzie ich niewiele.
Przykład.
W celu sprawdzenia poprawności sortowania kubełkowego
Tablicy wejściowa:
rozważmy dwa elementy A[i] i A[j].
A = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
Bez straty ogólności możemy założyć, że A[i] d" A[j].
Tablica B[0..9] posortowanych list (kubełków) po zakończeniu pętli
Ponieważ nA[i] d" nA[j] , element A[i] zostanie umieszczony
for w wierszach 4-5:
albo w tym samym kubełku co A[j], albo w kubełku o niższym
0.26
indeksie.
Ä™!
Jeśli A[i] i A[j] są w tym samym kubełku, to pętla for w wierszach
0.17 0.23 0.78
4-5 zapewni ustawienie ich we właściwej kolejności.
Ä™! Ä™! Ä™!
0.12 0.21 0.39 0.68 0.72 0.94
Jeśli A[i] i A[j] są w różnych kubełkach, to wiersz 6 zapewni
B = [ / Ä™! Ä™! Ä™! / / Ä™! Ä™! / Ä™! ]
ustawienie ich we właściwej kolejności.
Tak więc algorytm działa poprawnie.
Kubełek B[i] zawiera liczby z przedziału [i/10, (i + 1)/10).
/ oznacza pustą listę. Ciąg wynikowy powstaje przez połączenie
list w kolejności B[0], B[1], . . . , B[9].
Czas działania
Zauważmy, że łączny czas działania wszystkich instrukcji procedury
Załóżmy, że dane wejściowe zostały wybrane losowo z przedziału
BUCKET-SORT, oprócz wiersza 5, wynosi Ś(n).
[0, 1), zgodnie z rozkładem jednostajnym.
Niech ni będzie zmienną losową oznaczającą liczbę elementów
Oznacza to, że dla każdego i " {0, . . . , n - 1} i każdego
umieszczonych w kubełku B[i]. Sortowanie przez wstawianie ni
j " {1, . . . , n} element A[j] wpada do kubełka B[i] z jednakowym
2
liczb zajmuje czas Ś(ni ). Stąd łączny czas działania
prawdopodobieństwem równym 1/n. Zakładamy ponadto, że liczby
BUCKET-SORT wynosi
zostały wybrane niezależnie.
n-1

Zmienna losowa
2
T (n) = Åš(n) + Åš(ni ).

i=0
1 jeśli A[j] wpada do kubełka B[i]
Xij =
0 jeśli A[j] nie wpada do kubełka B[i]
Korzystając z własności wartości oczekiwanej (liniowość i
monotoniczność), mamy:
przyjmuje wartość 1 z prawdopodobieństwem 1/n.
n-1

Dla j = k zmienne Xij i Xik są niezależne.

2
E(T (n)) = Åš(n) + Åš(E(ni )).
i=0
2
Pokażemy, że E (ni ) = 2 - 1/n.
n

Mamy ni = Xij,
j=1
n
ëÅ‚ öÅ‚2

1 1 1 1 1
n n 2

E(ni ) = + = n · + n(n - 1) = 2 - .
2 2
íÅ‚
n n2 n n2 n
ni = Xijłł = Xij + XijXik,
j=1 1d"jd"n 1d"kd"n

j=1 j=1 1d"jd"n 1d"kd"n k=j
k=j

WstawiajÄ…c do wzoru na E (T (n)) mamy:
n

2 2
E(ni ) = E(Xij ) + E(XijXik),
n-1

j=1 1d"jd"n 1d"kd"n 2
E (T (n)) = Åš(n) + Åš(E(ni )) = Åš(n) + nÅš(2 - 1/n)
k=j

i=0

1 1 1
2
E(Xij ) = 1 · + 0 · 1 - = .
E(T (n)) = Åš(n).
n n n
Ponieważ dla k = j zmienne Xij i Xik są niezależne, zatem

Tak więc algorytm sortowania kubełkowego działa w oczekiwanym
czasie Ś(n) dla danych wejściowych rozmiaru n.
1 1 1
E(XijXik) = E(Xij)E(Xik) = · = .
n n n2