Kurs:Algorithmen und Datenstrukturen/Vorlesung/BucketSort

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Bucket Sort[Bearbeiten]

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[Bearbeiten]

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 ( ) in Bucket kommt.

Beispiel[Bearbeiten]

Als Eingabe haben wir 10 Zahlen (n=10) BucketSort

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

Algorithmus[Bearbeiten]

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[Bearbeiten]

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 wird aufgerufen, wobei die Anzahl dre Elemente in Bucket i ist.

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.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg