Bucketsort

Wusstest Du, dass Briefe in Deutschland im Grunde nach einem Sortierverfahren sortiert werden? Die Briefe aus den Briefkästen werden gesammelt und in Briefzentren gebracht. Dort werden sie zunächst nach den ersten zwei Zahlen ihrer Postleitzahl sortiert – damit ist das Briefzentrum des Zielortes gekennzeichnet. Dort werden die Briefe dann noch mal lokal nach Straße, Hausnummer usw. sortiert und verteilt.

Das Konzept, das bei den Sortieralgorithmen dahintersteckt, ist Bucketsort. Was es damit genau auf sich hat, erfährst Du hier.

Sortieralgorithmen Bucketsort

Das Grundprinzip hinter dem Bucketsort Sortieralgorithmus ist es, Datenmengen in sogenannte Buckets ("Eimer") zu verteilen. Diese Eimer werden dann mit einem anderen Sortieralgorithmus sortiert und anschließend wieder zu einer Liste zusammengeführt.

Bucketsort Definition

Wie der Bucketsort Algorithmus genau vorgeht, erfährst Du im folgenden Abschnitt.

Bucketsort Algorithmus

Am einfachsten lässt sich Bucketsort durch ein Beispiel erklären. Gegeben ist folgendes Array:

Schritt 1

Zunächst werden zehn verschiedene Buckets mit Indexen von 0 bis 9 angelegt. Die "Beschriftung" der Buckets ist dabei nicht vorgegeben, sprich, Du kannst die Buckets anwendungsbezogen benennen. Es wäre auch denkbar Ober- und Untergrenzen für einen Bucket zu definieren, anstatt einer konkreten Zahl.

Danach sortierst Du das gegebene Array in die einzelnen Buckets ein. Sortiert wird erst mal nur nach der ersten Nachkommazahl.

Schritt 2

Im zweiten Schritt wendest Du dann einen anderen Sortieralgorithmus an, um die Elemente innerhalb der einzelnen Buckets zu sortieren. In diesem Fall wird dafür Insertion Sort verwendet.

Beim gegebenen Beispiel musst Du lediglich die Buckets 2 und 7 genauer betrachten, da diese mehr als ein Element enthalten. Die Elemente in Bucket 2 sind bereits in der richtigen Reihenfolge, die Elemente in Bucket 7 müssen jedoch noch vertauscht werden.

Schritt 3

Der letzte Schritt ist dann, die einzelnen Buckets wieder zusammenzuführen – das wird auch Konkatenation genannt. Als Endergebnis erhältst Du ein vollständig sortiertes Array:

Bucketsort Vorgehensweise

Noch mal kurz und knapp, wie wird Bucketsort durchgeführt:

• Initialisiere Buckets und sortiere die gegebene Datenmenge hinein

• Wähle einen Sortieralgorithmus (z. B., Insertion Sort) und sortiere damit die einzelnen Buckets, falls notwendig

• Konkateniere die Buckets zu einem fertig sortierten Array

Bucketsort Komplexität

Bei der Komplexität müssen die Laufzeit (Zeitkomplexität) und der zusätzliche Speicherbedarf (Platzkomplexität) unterschieden werden.

Bucketsort Laufzeit

Die Laufzeit beim Bucketsort Sortieralgorithmus muss in Best-Case, Average-Case und Worst-Case unterschieden werden.

Best-Case

Der Best-Case geht davon aus, dass Datenmengen möglichst gleichmäßig in den einzelnen Buckets verteilt sind. Je nach verwendetem Sortieralgorithmus für das Sortieren in den Buckets, kann sogar eine lineare Komplexität erreicht werden (z. B. mit Insertion Sort). In diesem Fall würde die Laufzeit O(n + k) betragen.

Average-Case

Ist eine Datenmenge zufällig verteilt, liegt der Average-Case vor. Bucketsort läuft dabei ebenfalls in linearer Zeit ab – hat also eine Zeitkomplexität von O(n).

Worst-Case

Landen viele Elemente in den gleichen Buckets, hängt die Komplexität stark von dem Sortierverfahren ab, das die einzelnen Buckets sortiert. Befinden sich die Daten dann noch in der falschen Reihenfolge, verschlechtert sich die Laufzeit noch weiter.

Bucketsort Speicherbedarf

Bucketsort hat einen größeren Speicherbedarf als z. B. Insertion Sort oder Selection Sort. Außerdem arbeitet der Algorithmus out-of-place. Die Platzkomplexität ist dabei ebenfalls linear und beträgt O(n + k).

Bucketsort – Weitere Begrifflichkeiten

Weitere Begrifflichkeiten, die rund um Bucketsort erläutert werden sollen, sind:

• Stabilität

• Vergleichsbasiert

• Parallelisierbarkeit

Bucketsort stabil – instabil

Ob Bucketsort stabil ist, hängt vom verwendeten Verfahren innerhalb der Buckets ab. Wenn Du dort ein stabiles Sortierverfahren wie Bubble Sort oder Insertion Sort benutzt, ist auch Bucketsort stabil.

Bucketsort vergleichsbasiert

Bucketsort gehört zu den nicht vergleichsbasierten Sortieralgorithmen. Das heißt, es werden keine zwei Elemente direkt miteinander verglichen, um Datenmengen zu sortieren. Stattdessen werden die Daten vorsortiert und dann in ihren jeweiligen Buckets weiter sortiert.

Bucketsort Parallelisierbarkeit

Eine Parallelisierung ist beim Bucketsort Sortierverfahren ebenfalls umsetzbar. Am einfachsten kannst Du die Parallelisierbarkeit erreichen, indem Du jedem Bucket einen eigenen Prozessor zuweist.

Eine bessere Lösung wäre es, die Datenmengen vorher in einzelne Teilbereiche zu zerlegen und diese dann jeweils einem Prozessor zuzuweisen. Die Prozessoren würden dann ihre Liste in kleine Buckets einteilen und diese anschließend zur Einsortierung in die eigentlichen Buckets weiterschicken. Von dort aus werden die Daten dann endgültig sortiert und wieder zu einem Array zusammengefügt.

Bucketsort Zusammenfassung

In der folgenden Übersicht findest Du das bisher Gelernte auf einem Blick:

Bucketsort Vorteile

Das Bucketsort Sortierverfahren bringt verschiedene Vorteile:

Bedenke dabei, dass die Vorteile – und auch die Nachteile – vom zweiten verwendeten Sortieralgorithmus sowohl positiv als auch negativ beeinflusst werden können.

Bucketsort Nachteile

Neben Vorteilen hat Bucketsort auch Nachteile:

Bucketsort Beispiel

Nun folgen ein paar weitere (Code-)Beispiele zum Bucketsort.

Bucketsort Anwendung

Zunächst wird noch die Frage geklärt, wann Bucketsort angewendet wird:

• zum alphabetischen Sortieren von Wörtern
• bei Fließkommazahlen
• wenn Eingabedaten gleichmäßig über einen Bereich verteilt sind

Bucketsort Code

Wie könnte Bucketsort Code aussehen? Zunächst folgt etwas Pseudocode:

Bucketsort (liste, funktion)

  n = liste.size
  bucket = intervall(n)

// Elemente in Buckets vorsortieren
    for (element in liste)
      bucket[floor (funktion(element) * n].add(element)
  array []

// hier werden die Elemente in den Buckets mithilfe von Insertionsort sortiert
  for (daten in buckets)
    x.insertionsort(daten)
    array.append(x)

  return array

Jetzt folgt noch ein Beispiel, wie eine Implementation von Bucketsort in Java-Code aussehen könnte:

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {

  public void bucketSort(float[] arr, int n) {
    if (n <= 0)
      return;
    ArrayList[] bucket = new ArrayList[n];

    // Erzeuge leere Buckets
      for (int i = 0; i < n; i++)
      bucket[i] = new ArrayList();

    // Einfügen von Elementen in die Buckets 
    for (int i = 0; i < n; i++) {
      int bucketIndex = (int) arr[i] * n;
      bucket[bucketIndex].add(arr[i]);
    }

    // Sortieren der Elemente in jedem Bucket
    for (int i = 0; i < n; i++) {
      Collections.sort((bucket[i]));
    }

    // Sortiertes Array erzeugen 
    int index = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0, size = bucket[i].size(); j < size; j++) {
        arr[index++] = bucket[i].get(j);
      }
    }
  }

  // Treibercode
  public static void main(String[] args) {
    BucketSort b = new BucketSort();
    // Anlegen eines neuen Arrays mit unsortierten Daten
    float[] arr = { (float) 0.52, (float) 0.22, (float) 0.83, (float) 0.41, (float) 0.94, (float) 0.78,
        (float) 0.25, (float) 0.31, (float) 0.16, (float) 0.72 };
    // Funktion Buckesort aufrufen | arr = vorher definiertes Array mit Fließkommazahlen | n =7 
    b.bucketSort(arr, 10);
    // Sortiertes Array ausgeben lassen
    for (float i : arr)
      System.out.print(i + "  ");
  }
}

Ausgabe:

0.16 0.22 0.25 0.31 0.41 0.52 0.72 0.78 0.83 0.94