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.