Kurs:Algorithmen und Datenstrukturen/Vorlesung/Sortieren2 Nicht vergleichsbasiertes Sortieren




Bucket Sort Bearbeiten

Auf dieser Seite wird der Sortieralgorithmus BucketSort behandelt.

Idee Bearbeiten

Die Elemente kommen aus einem vorher festgelegtem Bereich, z.B. [1...K] für eine natürliche Zahl K und sie sind in [1...K] ungefähr gleich verteilt. 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 nehmen 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 reellen Zahlen aus dem Bereich [0,1) stammt. Die Aufteilung in Buckets erfolgt dadurch, dass Element e (  ) in Bucket   kommt.

Beispiel 1 Bearbeiten

Als Eingabe haben wir 10 Zahlen (n=10)  

Das Element e kommt in Bucket  . Das Bucket i ( ) enthält 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)

Beispiel 2 Bearbeiten

Als weiteres Beispiel ist K=100. Weiterhin haben wir als Eingabe folgende Folge:  . Sortiert man die Zahlen nun in die Buckets ein, sind die Zahlen danach folgend eingeordnet.

0-9 2
10-19 12
20-29 23
30-39 34 39
40-49
50-59 54 52
60-69 65
70-79
80-89 89
90-99 94

Von links nach rechts sind es verkettete Listen. Auf die einzelne Buckets, die mehr als ein Element besitzen, muss im Anschluss eventuell noch ein vergleichbasiertes Sortierverfahren angewandt werden. Wie es in diesem Beispiel beim Bucket von 50-59 der Fall ist.

Anschließend erhalten wir als Ausgabe:  .

Algorithmus Bearbeiten

void bucketSort(int[] f, int bound){
   int n = f.length;
   List<List<Integer>> buckets = createBuckets(n);
   for(int i = 0; i < n; i++)
      buckets.get(n*f[i]/bound).add(f[i]);
   int idx = 0;
   for(int i = 0; i < n; i++){
      quickSort(buckets.get(i));
      for(int j = 0; j < buckets.get(i).size(); j++)
         f[idx++] = buckets.get(i).get(j);
   }
}
List<List<Integer>> createBuckets(int n){
   List<List<Integer>> buckets 
      = new ArrayList<List<Integer>>();
   for(int i = 0; i < n; i++)
      buckets.add(new ArrayList<Integer>());
   return buckets;
}

Analyse Bearbeiten

Theorem der Terminierung Bearbeiten

Der Algorithmus BucketSort terminiert für jede Eingabe int[] f nach endlicher Zeit.

Beweis Bearbeiten

Alle Schleifenvariablen haben wohl-definierte Start- und Endpunkte.

Theorem der Korrektheit Bearbeiten

Das Theorem der Korrektheit besagt, dass nach Aufruf BucketSort(f,bound) f ein sortiertes Array mit gleichen Elementen wie vor dem Aufruf ist.

Beweis Bearbeiten

Sei i<j beliebig und betrachte f[i] und f[j] nach Anwendung BucketSort(f, bound). Falls n*f[i]/bound = n*f[j]/bound so  sind f[i] und f[j] im selben Bucket gelandet. Nach Annahme ist QuickSort korrekt und hat den Bucket korrekt sortiert.  Anschließend wurde zunächst f[i] und dann f[j] in das Array f geschrieben, also folgt f[i] ≤ f[j]. Fall n*f[i]/bound  ̸=    n*f[j]/bound so muss n*f[i]/bound < n*f[j]/bound gelten  (da i<j), daraus folgt direkt f[i] < f[j]. Also ist f sortiert. 

Theorem der Laufzeit Bearbeiten

Das Theorem der Laufzeit besagt, ist f mit n=f‐length ein Array mit Elementen, die gleich verteilt  sind in [1..bound] so hat BucketSort(f, bound) eine Laufzeit von  .

Beweis Bearbeiten

Im Schnitt landet in jedes Bucket genau ein Element (da  Gleichverteilung) und die Anwendung des  Sortieralgorithmus auf jedes Bucket (und die innerste  for‐Schleife) kann vernachlässigt werden. Alle anderen  Schleifen haben genau n Durchläufe, also  .  Falls die Annahme der Gleichverteilung nicht gilt,  wird keine lineare Komplexität erreicht. 

Aufwandsanalyse Bearbeiten

Die zugrunde liegende Annahme ist, dass die Eingabe-Elemente gleich verteilt auf [0,1) sind und wir somit eine uniforme Eingabeverteilung haben. Bzw. im Allgemeinfall ist f(e) gleich verteilt auf [0,1) Im Algorithmus werden n Elemente eingefügt und InsertionSort mit   wird aufgerufen, wobei   die Anzahl der Elemente in Bucket i ist.  

Bei gleich verteilter 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.