Bucketsort im Schnitt

Gegeben n-Schlüsseln $\in[0,1]$. Schlüsseln gleichverteilt. Um diese zu sortieren:

1.

Initialisiere Buckets $b_0,b_1,\cdots,b_n$

2.

Lege a_i in Bucket $\lceil n\cdot a_i \rceil$

3.

Sortiere Schlüssel innerhalb jedes Buckets

4.

Kankataniere Buckets

Beweis: Sei n_i die Anzahl der Elemente im Bucket b_i (nach Schritt 2). Die Schritte 1,2 und 4 benötigen zusammen die Zeit $\mathcal{O}(n)$. Die Zeit für Schritt 3 beträgt:

$$\mathcal{O}(\sum^{n}_{i=0}n^2_i)$$

Die Erwartungswert für $\sum n_i^2$ läßt sich folgendermaßen abschätzen:

$$\begin{split} \text{E}\left(\sum^{n}_{i=0} n^2_i\right) &\l... ... i < j \leq n}\frac{1}{n+1} \right)= \mathcal{O}(n).\end{split}$$

$\Diamond$