Bucketsort
aus Wikipedia, der freien Enzyklopädie
Bucketsort (von engl. bucket „Eimer“) ist ein stabiles Sortierverfahren, das eine Liste in linearer Laufzeit sortieren kann, da es nicht auf Schlüsselvergleichen basiert (siehe Sortierverfahren). Es arbeitet jedoch out-of-place.
Inhaltsverzeichnis |
[Bearbeiten] Voraussetzungen
Damit eine Liste mit Bucketsort sortierbar ist, muss die Anzahl der von den Sortierschlüsseln annehmbaren Werte endlich sein. Bucketsort ist also etwa gut geeignet, um eine lange Adressliste nach Postleitzahlen zu ordnen, aber nicht, um ein Personenverzeichnis nach Namen zu sortieren.
Vereinfacht wird die Implementierung, wenn die Sortierschlüssel ganze Zahlen sind, da sie dann als Indizes eines Feldes (Arrays) verwendet werden können. Ist dies nicht der Fall, so ist eine zusätzliche bijektive Funktion nötig, die jedem möglichen Schlüsselwert eine Zahl zuordnet, sowie die dazugehörige Umkehrfunktion.
[Bearbeiten] Prinzip
Bucketsort zählt die Häufigkeit jedes Schlüsselwertes in einer Liste. Daraus errechnet es die korrekte Position jedes Elements und fügt es in einer zweiten Liste dort ein.
Die Häufigkeit der Schlüsselwerte wird in einem so genannten Histogramm gespeichert. Dies wird meist als Array implementiert, das so lang ist, wie es mögliche Schlüsselwerte gibt; als Indizes werden dabei die Schlüsselwerte bzw. die ihnen zugeordneten ganzen Zahlen gewählt. Elemente mit gleichem Sortierschlüssel werden dabei in Gruppen, so genannten Buckets, zusammengefasst.
Das Histogramm wird zunächst mit Nullen initialisiert. Dann wird die zu sortierende Liste durchlaufen und bei jedem Listenelement der entsprechende Histogrammeintrag um eins erhöht.
In einem zweiten Array, das ebenso lang ist wie das Histogramm-Array und ebenfalls mit Nullen initialisiert wird, werden nun die aus dem Histogramm errechneten Einfügepositionen gespeichert.
Schließlich werden in eine Liste, die ebenso lang ist wie die zu sortierende, die Elemente der zu sortierenden Liste nacheinander an den berechneten Positionen eingefügt.
[Bearbeiten] Beispiel
Es liegt eine alphabetisch nach Namen geordnete Liste von Städten vor:
- Aachen (Nordrhein-Westfalen)
- Augsburg (Bayern)
- Bonn (Nordrhein-Westfalen)
- Bremerhaven (Bremen)
- Cuxhaven (Niedersachsen)
- Dresden (Sachsen)
- Erfurt (Thüringen)
- Essen (Nordrhein-Westfalen)
- Frankfurt am Main (Hessen)
- München (Bayern)
- Nürnberg (Bayern)
- Rosenheim (Bayern)
- Rostock (Mecklenburg-Vorpommern)
- Stuttgart (Baden-Württemberg)
- Wiesbaden (Hessen)
Diese Liste soll mit Bucketsort alphabetisch nach Bundesländern geordnet werden. Man benötigt nun zunächst eine Funktion, um jedem Bundesland einen Zahlenwert zuzuordnen, so wie es die folgende Tabelle zeigt:
| 0 | Baden-Württemberg | 8 | Niedersachsen | |
| 1 | Bayern | 9 | Nordrhein-Westfalen | |
| 2 | Berlin | 10 | Rheinland-Pfalz | |
| 3 | Brandenburg | 11 | Saarland | |
| 4 | Bremen | 12 | Sachsen | |
| 5 | Hamburg | 13 | Sachsen-Anhalt | |
| 6 | Hessen | 14 | Schleswig-Holstein | |
| 7 | Mecklenburg-Vorpommern | 15 | Thüringen |
Somit erhält man das in Abbildung 1 dargestellte Histogramm.
Aus dem Histogramm lassen sich die korrekten Einfügestellen ermitteln. Das Bucket 0 (Baden-Württemberg), das Stuttgart enthält, erhält die Einfügestelle 0.
Die vier bayerischen Städte in Bucket 1 sollen hinter Stuttgart, also ab Position 1, eingefügt werden. Bremerhaven aus Bucket 4 (Bremen) soll hinter den Buckets 1 und 2 eingefügt werden, also an Position 5. Fährt man fort, erhält man folgendes Array:
| Bucket | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Bundesland | BW | Bay | Ber | Bra | Bre | HH | Hes | MV | NS | NRW | RP | SL | Sac | SA | SH | Thü |
| Einfügestelle | 0 | 1 | 5 | 5 | 5 | 6 | 6 | 8 | 9 | 10 | 13 | 13 | 13 | 14 | 14 | 14 |
Nun wird das zu sortierende Feld durchlaufen: zunächst wird Aachen in der Zielliste an Position 10 gespeichert, da die Einfügeposition für den Bucket 9 (Nordrhein-Westfalen) 10 ist. Diese Einfügeposition wird daraufhin auf 11 erhöht, damit der nächste nordrhein-westfälische Ort hinter Aachen eingefügt wird.
Dann wird Augsburg an Position 1 der Zielliste gespeichert, denn dies ist die aktuelle Einfügeposition für Bucket 1 (Bayern). Diese Einfügeposition wird ebenfalls um eins erhöht.
Anschließend wird Bonn hinter Aachen an Position 11 gespeichert usw.
Man erhält die folgende Zielliste:
- Stuttgart (Baden-Württemberg)
- Augsburg (Bayern)
- München (Bayern)
- Nürnberg (Bayern)
- Rosenheim (Bayern)
- Bremerhaven (Bremen)
- Frankfurt am Main (Hessen)
- Wiesbaden (Hessen)
- Rostock (Mecklenburg-Vorpommern)
- Cuxhaven (Niedersachsen)
- Aachen (Nordrhein-Westfalen)
- Bonn (Nordrhein-Westfalen)
- Essen (Nordrhein-Westfalen)
- Dresden (Sachsen)
- Erfurt (Thüringen)
Wie man sieht, sind Städte, die im gleichen Bundesland liegen, untereinander alphabetisch nach den Städtenamen sortiert. Der Grund dafür ist, dass die ursprüngliche Liste nach Städtenamen sortiert war und Bucketsort stabil ist.
[Bearbeiten] Komplexität
Die asymptotische Laufzeit von Bucketsort ist abhängig von der Länge n der zu sortierenden Liste (im Beispiel: n=15) und der Anzahl k der Werte, die von den Sortierschlüsseln angenommen werden können (im Beispiel: k=16).
Für die Histogramm-Erstellung wird die zu sortierende Liste einmal durchlaufen. Die Komplexität wächst also linear mit der Länge der Liste. Die Aufwandsklasse der Histogramm-Erstellung ist also O(n).
Um die Einfügepositionen zu berechnen, wird das Histogramm einmal durchlaufen. Da das Histogramm-Array so lang ist, wie es mögliche Sortierschlüssel-Werte gibt, ist die Aufwandsklasse für die Erstellung des Einfügestellen-Arrays O(k).
Anschließend wird die zu sortierende Liste erneut durchlaufen, um die Elemente im Zielarray zu speichern. Die Aufwandsklasse ist erneut O(n).
Insgesamt ergibt sich für Bucketsort also eine Komplexität von O(n+k).
Die worst case Laufzeit und die best case Laufzeit des Algorithmus unterscheiden sich nicht voneinander, da der Bucketsort für alle gleichgroßen Eingabegrößen n immer gleich lange zur Berechnung braucht. Hierdurch ergibt sich, dass der Bucketsort in Θ(n) liegt.
Speichertechnisch ist der Algorithmus nur dann effektiv wenn k höchstens so groß wie n ist. Andernfalls wird für die Buckets mehr Speicher verbraucht als die Liste Elemente enthält.
[Bearbeiten] Variationen
Oft wird der Wertebereich der Schlüssel in Unterbereiche aufgeteilt, um die Anzahl der Buckets zu verringern (siehe auch Radixsort). In diesem Fall muss innerhalb der Buckets weiter sortiert werden. Hierzu kann wieder der Bucketsort herangezogen werden, oder jedes andere Sortierverfahren.
Manche Implementationen kommen ohne vorheriges Zählen und Aufaddieren aus, und gestalten die Buckets als einzelne Datenstrukturen variabler Größe (z.B. verkettete Listen), die im Anschluss der Reihe nach in das Ausgabearray geschrieben werden.
[Bearbeiten] Implementierung
[Bearbeiten] Java
Gegeben seien n natürliche Zahlen, die sortiert werden sollen. Sie werden in einem Array z[] gespeichert, für das gelte: 0 ≤ z[i] < anzahlBuckets. Weiterhin gebe es ein ausreichend großes Array buckets[].
void bucketsort(int n, int anzahlBuckets, int z[]) {
// histogramm erstellen
int buckets[] = new int[anzahlBuckets];
for (int i=0; i<anzahlBuckets; i++) {
buckets[i] = 0;
}
for (int i=0; i<n; i++) {
buckets[z[i]]++;
}
// sortieren
int x=0;
for (int i=0; i<anzahlBuckets; i++) {
while (buckets[i] > 0) {
z[x++] = i;
buckets[i]--;
}
}
}
[Bearbeiten] Pascal
Gegeben seien n natürliche Zahlen, die sortiert werden sollen. Sie werden in einem Array F[i] gespeichert, für das gelte: 0 ≤ F[i] ≤ m. Weiterhin gebe es ein ausreichend großes Array F2[].
for i:=1 to m do F2[i]:=0;
for i:=1 to n do F2[F[i]]:=F2[F[i]]+1;
x:=1;
for i:=1 to m do begin
while (F2[i]>0) do begin
F[x]:=i;
F2[i]:=F2[i]-1;
x:=x+1;
end;
end;
