Eimer-Sortierung

Bucketsort ist ein verteilungsbasiertes Sortierverfahren und kein vergleichsbasiertes Sortierverfahren. Es verteilt Werte auf geordnete Buckets, sortiert die Werte innerhalb jedes Buckets und fügt die Buckets anschließend in ihrer Reihenfolge zusammen, um das Ergebnis zu erhalten. Besonders gut eignet es sich, wenn die Werte gleichmäßig über einen bekannten Bereich verteilt sind. Dieser Verteilungs- und Sammelansatz ist nützlich, wenn sich die Werte passend auf Buckets abbilden lassen.

Bucketsort-Algorithmus

Wählen Sie k Buckets, die den Eingabebereich abdecken, und ordnen Sie anschließend jeden Wert dem Bucket für sein Intervall zu. Für Werte in [0, 1) ist floor(k * x) eine praktische, bei null beginnende Zuordnungsregel: Bucket j deckt [j/k, (j+1)/k) ab. Die obere Grenze ist ausgeschlossen, sodass jeder zulässige Wert einem Index von 0 bis k - 1 zugeordnet wird. Werte außerhalb dieses Bereichs müssen normalisiert oder mit einer anderen Zuordnungsregel behandelt werden; die Formel ist nicht universell.

Das Verfahren läuft so ab:

1. Erstellen Sie k Buckets für den gewählten Bereich.
2. Gehen Sie jeden Eingabewert x durch und legen Sie ihn in Bucket floor(k * x) ab.
3. Sortieren Sie jeden Bucket separat. Für kleine Buckets wird häufig Insertionsort verwendet; auch andere lokale Sortierverfahren sind möglich.
4. Durchlaufen Sie die Buckets in Indexreihenfolge und fügen Sie ihre sortierten Werte an das Ergebnis an.

Die Zuordnung zu den Buckets erhält die Reihenfolge zwischen ihnen: Jeder Wert in Bucket j ist kleiner als jeder Wert in Bucket j + 1. Das Sortieren innerhalb jedes Buckets ordnet die Werte, die dasselbe Intervall teilen. Der oben verlinkte Artikel über Insertionsort erklärt ein einfaches lokales Sortierverfahren; die folgende Implementierung verwendet stattdessen die sort-Funktion der C++-Standardbibliothek.

Bucketsort-Beispiel

Verwenden Sie zehn gleich große Intervalle über [0, 1), sodass sich der Index mit floor(10 * x) berechnet. Die Intervalle sind [0.0, 0.1), [0.1, 0.2) und so weiter bis [0.9, 1.0). Insbesondere kommt 0.1 in Bucket 1, weil der linke Endpunkt zu diesem Intervall gehört.

Für die Eingabe (0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31) ergibt sich folgende Verteilung:

Nach dem Sortieren enthält Bucket 2 die Werte 0.21, 0.22 und Bucket 3 die Werte 0.31, 0.33, 0.38; in den übrigen nicht leeren Buckets liegt jeweils ein Wert. Werden die Buckets von 0 bis 9 zusammengefügt, ergibt sich aufsteigend (0.1, 0.21, 0.22, 0.31, 0.33, 0.38, 0.45, 0.55).

Implementierung des Bucketsort-Algorithmus

Dieses C++-Programm verwendet dieselben acht Werte wie oben. Es verteilt sie auf zehn Buckets, sortiert jeden Bucket und gibt die zusammengeführte Folge aus. Das im Ausgabebeispiel sichtbare Label „Sorted values:“ bleibt unverändert auf Englisch.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

std::vector<double> bucketSort(const std::vector<double>& values,
                               std::size_t bucketCount) {
    std::vector<std::vector<double>> buckets(bucketCount);

    for (double value : values) {
        const std::size_t index = static_cast<std::size_t>(value * bucketCount);
        buckets[index].push_back(value);
    }

    std::vector<double> result;
    result.reserve(values.size());
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
        result.insert(result.end(), bucket.begin(), bucket.end());
    }
    return result;
}

int main() {
    const std::vector<double> values = {0.22, 0.33, 0.1, 0.45,
                                        0.38, 0.55, 0.21, 0.31};
    const std::vector<double> sorted = bucketSort(values, 10);

    std::cout << "Sorted values:";
    for (double value : sorted) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
    return 0;
}

Sorted values: 0.1 0.21 0.22 0.31 0.33 0.38 0.45 0.55

Die Funktion setzt voraus, dass bucketCount positiv ist und jeder Wert in [0, 1) liegt. Dadurch bleibt der berechnete Index innerhalb des Bucket-Vektors. Für einen anderen Wertebereich müssen Sie die Werte vor der Indexberechnung normalisieren oder eine dafür geeignete Zuordnungsregel festlegen. Die bereitgestellten Laufzeitdaten dokumentieren, dass dieses Programm erfolgreich mit Exit-Code 0 ausgeführt wurde und die oben gezeigte sortierte Folge ausgegeben hat.

Komplexität des Bucketsort-Algorithmus

Sei n die Anzahl der Werte, k die Anzahl der Buckets und b_j die Anzahl der Werte in Bucket j. Das Erstellen der Buckets und Verteilen der Werte benötigt O(n + k) Zeit. Wird in jedem Bucket ein vergleichsbasiertes Sortierverfahren wie std::sort verwendet, ist der zusätzliche Aufwand durch die Summe der lokalen Sortierkosten begrenzt, also durch O(Σ b_j log b_j). Ein einzelner stark gefüllter Bucket kann die Gesamtlaufzeit daher auf O(n log n) bringen. Erwartetes, nahezu lineares Verhalten ist möglich, wenn die Werte so verteilt sind, dass die Buckets klein bleiben — häufig bei k proportional zu n und einer annähernd gleichmäßigen Eingabeverteilung. Allein die Bezeichnung des Algorithmus garantiert das nicht.

Wird innerhalb der Buckets Insertionsort verwendet, kann ein Bucket der Größe b_j im schlimmsten Fall O(b_j²) Zeit benötigen. Ein stark gefüllter Bucket kann die Gesamtlaufzeit dann quadratisch machen. Deshalb spielen sowohl das lokale Sortierverfahren als auch die Eingabeverteilung für die Leistungsschätzung eine Rolle.

Der zusätzliche Speicherbedarf beträgt O(n + k): Die Buckets speichern die n Werte, und die Bucket-Struktur selbst umfasst k Einträge. Dies entspricht dem Speicherbedarf der Implementierung, die einen separaten sortierten Vektor zurückgibt. Der Aufwand beträgt nicht O(n * k), da jeder Wert in genau einem Bucket gespeichert wird und nicht in alle Buckets kopiert wird.