Bucketsort

BucketSort (von engl. bucket - Eimer) ist ein schnelles, stabiles Sortierverfahren, das eine Liste in linearer Laufzeit sortieren kann, jedoch out-of-place arbeitet.

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, da die Zahl der denkbaren Namen praktisch unendlich ist.

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.

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.

Beispiel

Es liegt eine alphabetisch nach Namen geordnete Liste von Städten vor:

1. Aachen (Nordrhein-Westfalen)
2. Augsburg (Bayern)
3. Bonn (Nordrhein-Westfalen)
4. Bremerhaven (Bremen)
5. Cuxhaven (Niedersachsen)
6. Dresden (Sachsen)
7. Erfurt (Thüringen)
8. Essen (Nordrhein-Westfalen)
9. Frankfurt am Main (Hessen)
10. München (Bayern)
11. Nürnberg (Bayern)
12. Rosenheim (Bayern)
13. Rostock (Mecklenburg-Vorpommern)
14. Stuttgart (Baden-Württemberg)
15. 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

Abb. 1: Histogramm

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:

1. Stuttgart (Baden-Württemberg)
2. Augsburg (Bayern)
3. München (Bayern)
4. Nürnberg (Bayern)
5. Rosenheim (Bayern)
6. Bremerhaven (Bremen)
7. Frankfurt am Main (Hessen)
8. Wiesbaden (Hessen)
9. Rostock (Mecklenburg-Vorpommern)
10. Cuxhaven (Niedersachsen)
11. Aachen (Nordrhein-Westfalen)
12. Bonn (Nordrhein-Westfalen)
13. Essen (Nordrhein-Westfalen)
14. Dresden (Sachsen)
15. 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.

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.

Implementierung

...