Bucket Sort

Auf dieser Seite wird der Sortieralgorithmus BucketSort behandelt. Die bisherigen Verfahren sortieren n Zahlen mit n · log n Vergleichen, z.B. QuickSort im Durchschnittsfall. Die Sortierung wurde durch Vergleiche und VergleichSortierung bestimmt. Wir haben gezeigt, dass n log n ist eine untere Schranke für Sortieralgorithmen die auf Vergleiche und Elementvergleich basieren ist. Doch geht es auch besser? BucketSort sortiert mit linearem Aufwand, aber Annahmen über die Eingabe und die Verteilung.

Idee

Als Eingabe haben wir n Elemente und eine Funktion f die auf den Wertebereich [0,1) abbildet. f(e) ist dann der Sortierschlüssel der Elemente e. Vereinfacht haben wir als Eingabe n Elemente aus dem Wertebereich [0,1), das heißt wir nehmen die Anwendung von Funktion f bereits an. Es wird eine n verkettete Liste erzeugt (buckets), die das Intervall [0,1) in n Teilintervalle der Größe 1/n einteilen. Das bedeutet die Wertebereiche werden in n gleich große Teilintervalle zerlegt. Als nächstes wird jedes Element in die passende Liste eingefügt und danach werden die Listen verkettet. WIr nehemen an, dass die Funktion f eine Eingabe aus n Zahlen in n reellen Zahlen im Bereich [0,1)abbildet. Die Vereinfachte Variante ist, dass die Eingabe der n reelen Zahlen aud dem Bereich [0,1) stammt. Die Aufteilung in Buckets erfolgt dadurch, dass Element e ( $e\in [0,1)$ ) in Bucket $e\cdot n$ kommt.

Beispiel

Als Eingabe haben wir 10 Zahlen (n=10)

Das Element e kommt in Bucket $e\cdot n$ . Das Bucket i ( $0\leq i<n$ ) enthällt Werte in $[i/n,(i+1)/n)$ . Für den Fall mit n=10 kommt das Element e in Bucket $e\cdot 10$ . Beispielsweise 0,17 in 1. Das Bucket i enthält Werte in $[i/10,(i+1)/10)$ , z.B. i=1:[1/10,2/20)

Algorithmus

void bucketSort(double[] F) {
 
      int n = F.l engt h; 
      for (int i = 0; i < n ; i++)
             insert F[hi] into bucket B[⌊n F[i]⌋]; 
      for (int i = 0; i<n; i++)
             insertionSort(B[i]); 
      concatenate(B[0], …, B[n-1]);
 
}

Aufwand

Die zugrundeliegende Annahme ist, dass die Eingabe-Elemente gleichverteilt auf [0,1) sind und wir somit eine uniforme Eingabeverteilung haben. Bzw. im Allgemeinfall ist f(e) gleichverteilt auf [0,1) Im Algorithmus werden n Elemente eingefügt und InsertionSort mit $m_{1},...,m_{n}$ wird aufgerufen, wobei $m_{i}$ die Anzahl dre Elemente in Bucket i ist. $T(n)=O(n)+\sum _{i=0}^{n-1}O(m_{i}^{2})$

Bei gleichverteilter Eingabe liegt O(n) vor. Die Abschätzung ist intuitiv, da wir n Elemente auf n Buckets verteilen! Wir erwarteten 1 Elemente je Bucket(genauer: O(1) – d.h. konstant). Das Sortieren (z.B. InsertionSort) je Bucket ist dann O(1). Da wir n buckets haben, muss n-mal sortiert werden. Falls die Annahme der Gleichverteilung nicht gilt, wird keine lineare Komplexität erreicht.