- 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:
- Verteilung der Elemente auf die Buckets (Partitionierung)
- Jeder Bucket wird mit einem weiteren Sortierverfahren, wie beispielsweise Insertionsort sortiert.
- Der Inhalt der sortierten Buckets wird konkateniert.
Das Verfahren arbeitet also out-of-place.
Inhaltsverzeichnis
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
Wikimedia Foundation.