Bucketsort
Bucketsort (von engl. bucket „Eimer“) ist ein Sortierverfahren, das für bestimmte Werte-Verteilungen eine Eingabe-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.
1 Algorithmus
2 Komplexität
Algorithmus[Bearbeiten]
Die Eingabe von Bucketsort ist eine Liste mit Elementen und eine Funktion , die jedes Element der Liste in das Intervall abbildet. Die Ausgabe ist eine sortierte Liste, wobei den Sortierschlüssel von einem Element berechnet. Während der Sortierung verwendet der Algorithmus „Buckets“, die in einem Array angeordnet sind. Die Verteilung der Elemente geschieht über dieses Array, indem jedes Element in den -ten Bucket gelegt wird. Danach wird nacheinander jeder Bucket sortiert. In der letzten Phase werden die Bucket-Listen in der Reihenfolge, wie sie im Array angeordnet sind, konkateniert, was als Ergebnis die sortierte Ausgabe darstellt.
Als Pseudo-Code:
bucket_sort(l, f)
n = l.size
buckets = array(n)
foreach (e in l)
buckets[ floor(f(e) * n) ].add(e)
r = []
foreach (b in buckets)
x = insertion_sort(b)
r.append(x)
Der Algorithmus sortiert stabil, wenn der für die Sortierung der Buckets verwendete Sortier-Algorithmus, hier insertion_sort, stabil ist.
Komplexität[Bearbeiten]
Die Verteilung der Funkti