Theoretische Informatik

Bucketsort

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:

  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.

Bucketsort
direkt ins Video springen
Bucketsort

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.

Bucketsort Beispiel
direkt ins Video springen
Bucketsort Beispiel

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 O(n)+ \sum_{i=0}^{n-1} O(l \cdot log \cdot l).

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 O(n). 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. O(n) entspricht dabei auch gleichzeitig dem Average-Case.

Im Falle der Verwendung eines Mergesorts als angewendetes Sortierverfahren innerhalb eines Buckets, beträgt die Laufzeitkomplexität O(n \cdot log \cdot n).

Die Speicherplatzkomplexität ist O(n).

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.