Załóżmy teraz, że elementy, które chcemy posortować, są liczbami rzeczywistymi wybranymi losowo, z rozkładem jednostajnym, z przedziału [0,1).

Podzielmy przedział [0,1) na n podprzedziałów o takiej samej długości. Każdy przedział traktujemy jako "kubełek", do którego wkładamy te elementy danego ciągu, które należą do odpowiadającego "kubełkowi" przedziału. Każdy z "kubełków" sortujemy osobno, a następnie zawartości "kubełków" łączymy w jeden ciąg.

Niech 0.9, 0.32, 0.74, 0.15, 0.23, 0.21, 0.17, 0.45, 0.28 będzie ciągiem, który chcemy posortować. W poniższej tablicy przedstawiamy stan "kubełków" po rozrzuceniu wszystkich elementów.

Wprawdzie spodziewamy się, że średnio w każdym "kubełku" jest tylko jeden element, ale nie musi tak być. W algorytmie BucketSort, realizującym opisaną wyżej metodę, zaproponowano użycie algorytmu InsertionSort do sortowania zawartości "kubełków".

Niech dany do posortowania ciąg e₁,...,e_n będzie zapisany w tablicy e[1],...,e[n] i niech spełnione będą warunki 0 £ e[i] <1. Zakładamy ponadto , że mamy do dyspozycji pomocniczą tablicę L, n list, L[0],...,L[n-1], które będą pełniły rolę "kubełków". Wynikiem działania algorytmu będzie wypisanie elementów danego ciągu e₁,...,e_n w porządku niemalejącym.

BucketSort{
	for i := 1 to n do
	dopisz e[i] do listy L[ ën´e[i]û]	// rozrzuć wszystkie liczby do "kubełków"
	od;
	for i := 0 to n-1 do
	posortuj listę L[i] algorytmem InsertionSort	//posortuj każdy z "kubełków" osobno
	od;
	Wypisz kolejno elementy list L[0],L[1],..., L[n-1]	//połącz "kubełki"
}

Dla dowodu poprawności przedstawionego algorytmu sprawdźmy przede wszystkim, czy elementy ciągu e trafiają do właściwej listy. Ponieważ przedział [0, 1) został podzielony na równe części, zatem lista L[i] odpowiada przedziałowi [i/n, (i+1)/n). Liczba e[i] powinna się więc znaleźć w "kubełku" j-tym, jeżeli j/n £ e[i] < (j+1)/n. Mamy

Przyjmując j = ën´e[i]û i umieszczając e[i] na liście L[ën´e[i]û] otrzymamy częściowe posortowanie danego ciągu. Możemy więc stwierdzić, że po wykonaniu pierwszej pętli "for" prawdziwa jest własność: każdy element danego ciągu znajduje się na dokładnie jednej z list L[0],..., L[n-1], oraz elementy listy L[i] są mniejsze od wszystkich elementów listy L[i+1], dla i = 0,1,...,n-1.

Przyjmując, że algorytm InsertionSort sortuje poprawnie elementy każdego "kubełka" w porządku niemalejącym, po wypisaniu kolejno elementów list L[0],...,L[n-1] otrzymamy ciąg uporządkowany niemalejąco.

Twierdzenie 6.1 Dla dowolnych danych spełniających warunek początkowy { 0 £ e[i] < 1} w strukturze liczb rzeczywistych algorytm BucketSort zatrzymuje się, a wypisany w wyniku działania algorytmu ciąg, jest uporządkowaną niemalejąco permutacją elementów danego ciągu.

Zauważmy, że koszt pierwszej pętli i koszt wypisania zawartości wszystkich list jest liniowy Q(n), dla ciągu n elementowego. Pozostaje zbadać koszt związany z sortowaniem list. Algorytm InsertionSort jest wprawdzie algorytmem o złożoności kwadratowej, ale nie spodziewamy się dużej liczby elementów w jednym "kubełku". Jeżeli n[j] jest liczbą elementów w j-tej liście, to koszt algorytmu BucketSort można oszacować następująco:

Załóżmy, że każdy element danego ciągu wpada do dowolnego kubełka z takim samym prawdopodobieństwem. Można wtedy pokazać, że wartość oczekiwana kwadratu liczby elementów w j-tym "kubełku" wynosi E(n[j]²)= 2-1/n. Stąd, wartość oczekiwana liczby wykonanych operacji w algorytmie BucketSort wynosi Q(n) + n ( 2-1/n) i jest liniowa względem rozmiaru danych.

Pytanie 7 : Jaki jest pesymistyczny czas działania algorytmu BucketSort, zastosowanego do n elementowego ciągu?

Dane:		0.32	0.74	0.15	0.23	0.21	0.17	0.45	0.28	0.43	0.90	S O R T O W A N I E

K U B E Ł K I	L[0]	®					L[0]	®
	L[1]	®	.15	.17			L[1]	®	.15	.17
	L[2]	®	.23	.21	.28		L[2]	®	.21	.23	.28
	L[3]	®	.32				L[3]	®	.32
	L[4]	®	.45	.43			L[4]	®	.43	.45
	L[5]	®					L[5]	®
	L[6]	®					L[6]	®
	L[7]	®	.74				L[7]	®	.74
	L[8]	®					L[8]	®
	L[9]	®	.90				L[9]	®	.90
po rozrzuceniu							po posortowaniu

Po połączeniu kubełków				.15	.17	.21	.23	.28	.32	.43	.45	.74	.90