Der Bucketsort (von englisch bucket “Eimer”) ist Sortieralgorithmus, der ohne Vergleichen funktioniert.
Das Verfahren erfolgt dabei in drei Schritten:
- Zuerst erstellen wir sogenannte Buckets, in die wir dann die Elemente ablegen.
- Jeder Eimer wird anschließend separat sortiert, z.B. mit einem vergleichsbasierten Sortierverfahren wie Insertionsort oder Mergesort.
- Der Inhalt der einzelnen Buckets wird wieder zusammengeführt.
Activity
Wir schauen uns das an einem Beispiel an. In einer unsortierten Liste haben wir Zahlen zwischen 0 und 99.
Als erstes müssen wir die Buckets festlegen, in die wir sortieren wollen. In diesem Fall wollen wir gerne anhand der ersten Ziffer der Zahl unterscheiden. Dann legen wir die Zahlen in den Buckets ab.
Ziehe dazu die Zahlen auf den entsprechenden Eimer.
Im nächsten Schritt werden die Elemente in den einzelnen Buckets sortiert. Da hier nun nur noch wenige Elemente zu sortieren sind, dauert das nicht lange. Das kannst du am folgenden Beispiel sehen.
Im letzten Schritt setzen wir die sortierten Elemente aus den Buckets zu einer vollständig sortierten Liste zusammen.
Ziehe dazu die Zahlen aus den Buckets und ordne sie darunter in der richtigen Reihenfolge an.
Wie schnell mit dem Bucketsort sortiert werden kann, hängt davon ab, wie gleichmäßig die Elemente auf die Buckets verteilt werden können. Sind in allen Buckets ungefährt gleich viele Elemente, dann hängt die Laufzeit linear mit der Eingabegröße zusammen ( = O(n)). Falls aber in wenigen Buckets sehr viele Elemente landen, dann hängt die Laufzeit des gesamten Verfahrens davon ab, wie schnell innerhalb dieser Buckets sortiert wird. Wird beispielsweise in den Buckets mit Mergesort sortiert, ergibt sich für das ganze Verfahren eine Komplexität in O(n * log n).
Der Bucketsort benötigt zusätzlichen Speicherplatz für die Buckets. Solch ein Verfahren nennt man out-of-place-Sortierevrfahren. In-place-Verfahren, wie der Bubblesort, schieben die Elemente innerhalb der gegebenen Liste hin und her, und brauchen deshalb keinen weiteren Speicherplatz. Wie viel Speicherplatz für den Bucketsort benötigt wird, hängt linear von der Eingabegröße ab (=O(n)).
Der Bucketsort ist stabil, sofern der Algorithmus, der für die einzelnen Buckets verwendet wird, auch stabil ist.
Ein stabiler Sortieralgorithmus lässt Werte, die gleich groß sind, in ihrer ursprünglichen Reihenfolge stehen. Das kann zum Beispiel interessant sein, wenn Elemente nach verschiedenen Kriterien sortiert werden können und eine vorherige Sortierung nicht aufgehoben werden soll.
Hier siehst du in Pseudocode, wie der Algorithmus implementiert werden kann.
BUCKETSORT(A, f)
DEFINIERE k // Anzahl der Buckets
SETZE buckets array MIT k EINTRÄGEN
JEDER EINTRAG VON buckets SEI array MIT UNBESTIMMT VIELEN EINTRÄGEN
n = Länge(A)
FÜR i=0,…,n-1
FÜGE A[i] ZU buckets[abrunden(f(i)*k)] HINZU
LEERE array A
FÜR i=0,…k-1
SORTIERE(buckets[i])
FÜGE buckets[i] ZU A HINZU
RETURN A