Bucketsort

Bucketsort (von engl. bucket „Eimer“) ist ein Sortierverfahren, das eine gleichverteilte Werte-Liste in linearer Zeit sortiert. Der Algorithmus ist in drei Phasen eingeteilt:

1. Verteilung der Elemente auf die Buckets (Partitionierung)
2. Jeder Bucket wird mit einem weiteren Sortierverfahren, wie beispielsweise Insertionsort sortiert.
3. Der Inhalt der sortierten Buckets wird konkateniert.

Das Verfahren arbeitet also out-of-place.

Voraussetzungen

Den zu sortierenden Elementen muss ein Wert zugeordnet werden können. Damit der Algorithmus im Worst-Case eine lineare Laufzeit hat, muss die Verteilung der Werte eine Gleichverteilung sein.

Algorithmus

bucket_sort(l, f){
  n = l.size()
  buckets = array(n)
  r = []
  foreach (e in l){
    buckets[ floor(f(e) * n) ].add(e)
  }
  foreach (b in buckets){
    x = insertion_sort(b)
    r.append(x)
  }
 return r
}

Der Sortiertalgorithmus ist in der Pseudocode-Funktion bucket_sort spezifiziert. Die Eingabe ist die zu sortierende Liste l und eine Funktion f. Diese Funktion f ordnet jedem Element der Liste einen Wert in dem Intervall [0,n] zu. Die Funktion bucket_sort gibt die sortierte Liste zurück.

Der Algorithmus sortiert stabil, wenn der für die Sortierung der Buckets verwendete Sortier-Algorithmus, hier insertion_sort, stabil ist.

Komplexität

Die Laufzeit des Algorithmus liegt im Worst-Case in O(n), wenn die Eingabedaten gleichverteilt sind und n die Länge der Liste bezeichnet. Denn bei einer Eingabelänge von n Elementen und n Buckets enthält jeder Bucket nach der Partitionierung O(1) Elemente.

Falls die Eingabe nicht gleichverteilt ist, dann entspricht die Laufzeit der Laufzeit des Sortier-Algorithmus, der zur Sortierung eines Buckets verwendet wird. Ein solcher Worst-Case tritt ein, wenn beispielsweise alle Elemente in einen Bucket eingeteilt werden.

Der Speicherbedarf liegt in O(n).

Literatur

• Cormen et. al.: Introduction to Algorithms. 2. Auflage. MIT Press, 2001, ISBN 0-262-03293-7, S. 174.

Siehe auch

• Hybridsort, ein Sortierverfahren, das die Eigenschaften von Bucketsort und Heapsort kombiniert.
• Countingsort
• Radixsort