Bucketsort

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:

1. Zuerst erstellen wir sogenannte Buckets, in die wir dann die Elemente der unsortierten Liste verteilen und ablegen.
2. Jeder einzelne dieser Eimer wird dann mit einem weiteren Sortierverfahren sortiert. Diese können etwa der Mergesort oder der Insertionsort
3. 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.

direkt ins Video springen

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.

direkt ins Video springen

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.

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 ausgabearray

Komplexitä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 .