Hier findest du eine ausführliche Bucketsort Erklärung. Zuerst erfährst du alles wichtige über das Prinzip des Sortierverfahrens. Darauf aufbauend zeigen wir dir ein Bucketsort Beispiel. Danach erklären wir dir den allgemeinen Algorithmus und wie du ihn als Pseudocode darstellen kannst. Zum Schluss erfährst du alles Wichtige zur Laufzeit.
Inhaltsübersicht
Grundidee
Der Bucketsort ist ein nicht-vergleichsbasierter Sortieralgorithmus in der Informatik. Er sortiert eine Liste von gleichmäßig verteilten Elementen sehr schnell in linearer Zeit. Das Verfahren erfolgt dabei in drei Schritten:
- Zuerst erstellen wir sogenannte Buckets, in die wir dann die Elemente der unsortierten Liste verteilen und ablegen.
- Jeder einzelne dieser Eimer wird dann mit einem weiteren Sortierverfahren sortiert. Diese können etwa der Mergesort oder der Insertionsort
- Der Inhalt der einzelnen Buckets wird dann durch eine Konkatenation zu einer neuen Gesamtliste zusammengefügt.
Da der Sortieralgorithmus Zwischenspeicher verwendet, arbeitet das Sortierverfahren somit out-of-place.
Bucketsort Beispiel
Im Folgenden baut sich ein Bucketsort Beispiel auf, dafür sind die folgenden zehn Zahlen gegeben:
0.84 0.68 0.16 0.21 0.12 0.91 0.81 0.24 0.44 0.52
Zuerst werden zehn verschiedene Eimer erstellt, die mit den Zahlen 0 bis 9 beschriftet werden.
Im nächsten Schritt müssen die Zahlen in die richtigen Buckets einsortiert werden. Beim ersten Durchlauf wird dabei nur die erste Nachkommastelle. Entsprechend wird beispielsweise die Zahl 0.84 in den Eimer mit der Nummer 8 einsortiert. Die zweite Zahl wird nach demselben Prinzip in den sechsten Eimer gelegt und alle weiteren Elemente werden analog zugeordnet. Wichtig dabei ist, dass Elemente innerhalb eines Eimers in derselben Reihenfolge angeordnet werden wie in der ursprünglichen Liste. Die 0,84 liegt also vor der 0,81 im achten Eimer. Am Ende sieht das Ganze dann so aus.
Nun gehen wir zu Schritt zwei über. Dabei wird der Insertionsort als zweites Sortierverfahren zum Sortieren des Buckets verwendet. Hierbei werden die Inahlte in den Buckets 1 und 8 vertauscht.
Am Ende müssen alle Inhalte der Eimer durch Konkatenation wieder zu einer Gesamtliste zusammengefügt werden, wodurch ein neuer, sortierter Array entsteht.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
Algorithmus
Der Bucketsort Algorithmus lässt sich also folgendermaßen darstellen.
Für den Sortiervorgang wird einerseits eine zu sortierende Liste benötigt, zusätzlich aber auch eine Funktion, die jedes Element des Array einem Wert in dem Intervall [0,n] zuordnen kann. Die Liste selbst setzt sich dabei aus n-Elementen zusammen.
Zum Sortieren werden Buckets benötigt, die das Intervall [0,1) in n Teilintervalle mit der Größe 1/n unterteilen kann. Entsprechend kann damit dann jedes Element in den zugehörigen Eimer einsortiert werden. Für jeden Bucket wird dann für seine jeweiligen Inhalte ein Insertionsort durchgeführt. (Es kann auch ein Mergesort verwendet werden!) Die Inhalte werden dann mittels Konkatenation zu einer fertig sortierten Gesamtliste zusammengefügt.
Pseudocode
Bucketsort (liste, funktion)
n = liste.size
bucket = intervall(n)
for (element in liste)
bucket[floor (funktion(element) * n].add(element)
ausgabearray []
for (inhalt in buckets)
x.insertionsort(inhalt)
ausgabearray.append(x)
return ausgabearrayKomplexität
Zum Abschluss wird noch die Komplexität / Bucketsort Laufzeit erläutert. Diese hängt von mehreren Faktoren ab. Zum einen von der Verteilung der Funktionswerte. Dabei beträgt die O-Notation
.
Im günstigsten Fall sind die einzelnen Elemente annähernd gleichverteilt. Dann benötigt das Zuweisen in die Buckets, ebenso wie die Konkatenation eine Gesamtlaufzeit von 
. Bei anderen Werteverteilungen kann die Laufzeit jedoch vom Sortierverfahren, das für die einzelnen Listen verwendet wird, dominiert werden – also dem Insertionsort oder Mergesort. Die Komplexität wird also im Fall dieses Sortierverfahrens von verschiedenen Faktoren beeinflusst. entspricht dabei auch gleichzeitig dem Average-Case.
Im Falle der Verwendung eines Mergesorts
als angewendetes Sortierverfahren innerhalb eines Buckets, beträgt die Laufzeitkomplexität 
.
Die Speicherplatzkomplexität ist .
Bucketsort — häufigste Fragen
(ausklappen)
Bucketsort — häufigste Fragen
(ausklappen)-
Wie entscheidet Bucketsort, in welchen Bucket ein Element gehört?Bucketsort ordnet ein Element über eine Zuordnungsfunktion einem Teilintervall zu und legt es in den passenden Bucket. Üblich ist die Berechnung
bei 
Buckets. Zum Beispiel landet 0,84 bei 
im Bucket 8.
-
Ist Bucketsort stabil?Bucketsort ist stabil, wenn beim Verteilen die Reihenfolge innerhalb eines Buckets beibehalten wird und das Sortierverfahren im Bucket ebenfalls stabil ist. Dann bleiben gleich große Elemente nach dem Sortieren in der gleichen Reihenfolge wie vorher. Mit einem instabilen In-Bucket-Sort kann Bucketsort instabil werden.
-
Was bedeutet Out-of-Place bei Bucketsort?Out-of-place bedeutet bei Bucketsort, dass die Elemente nicht nur innerhalb der ursprünglichen Liste umsortiert werden, sondern zusätzlich in separate Buckets zwischengespeichert werden. Danach werden die Inhalte aus den Buckets in eine neue Gesamtliste zusammengefügt, wodurch extra Speicher benötigt wird.
-
Welche Laufzeit hat Bucketsort im schlechtesten Fall, wenn viele Werte im selben Bucket landen?Im schlechtesten Fall landet fast alles in einem Bucket, dann bestimmt das Sortieren dieses Buckets die Laufzeit von Bucketsort. Verwendet man dafür Insertionsort, kann die Laufzeit bis auf
steigen. Mit Mergesort im Bucket liegt sie bei 
.
Sortieralgorithmen verstehen
Bucketsort ist ein nicht vergleichsbasierter Sortieralgorithmus und gehört zum Themenfeld der Sortieralgorithmen. Wer sich mit Sortieralgorithmen beschäftigt, vergleicht verschiedene Verfahren nach Ablauf, Speicherbedarf und Laufzeit. So wird klar, warum manche Algorithmen bei bestimmten Daten besonders schnell arbeiten und andere allgemeiner einsetzbar sind. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.
