Bucketsort

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Bucketsort (von englisch bucketEimer“) ist ein Sortierverfahren, das für bestimmte Werte-Verteilungen eine Eingabe-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 Mergesort sortiert.
  3. Der Inhalt der sortierten Buckets wird konkateniert.

Das Verfahren arbeitet also out-of-place.

Die Eingabe von Bucketsort ist eine Liste mit Elementen und eine Funktion , die jedes Element der Liste in das halboffene Intervall monoton in der Weise abbildet, dass für sortiermäßig . Basiert die Sortierreihenfolge auf einem Vergleich binärer Daten, kann man die Bits mit der höchsten Signifikanz nehmen. 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, k)
   buckets = array(k)
   foreach (e in l)
     buckets[ floor(f(e) * k) ].add(e)
   r = []
   foreach (b in buckets)
     x = mergesort(b)
     r.append(x)
   return r

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

Die Verteilung der Funktionswerte von bestimmt die Laufzeit von Bucketsort. Die Laufzeit ist in (in O-Notation), wobei die Anzahl der Elemente im -ten Bucket bezeichnet. Bei einer Gleichverteilung ist die Gesamtlaufzeit in , da die Summe über die Buckets linear ist und ihre Summanden als konstant (bei exakter Gleichverteilung =1) angesehen werden können. Die effiziente Laufzeit von ist nicht nur bei einer Gleichverteilung gegeben, sondern bei allen Verteilungen, nach denen der Summenterm asymptotisch linear ist. Sie wird auch als Average-Case-Laufzeit angesehen.[1]

Bei anderen Werte-Verteilungen kann die Laufzeit des Bucketsortalgorithmus von der Laufzeit des Sortier-Algorithmus dominiert werden, der zur Sortierung eines Buckets verwendet wird. Ein solcher Worst-Case tritt beispielsweise ein, wenn alle Elemente einem einzigen Bucket zugeordnet werden. Bei Verwendung von mergesort für die Sortierung der Buckets ist die Gesamtlaufzeit dann in .

Natürlich lässt sich diese Sortierung zweiter Stufe wieder als Bucketsort implementieren, dann mit Sub-Buckets pro Bucket. Diese Vorgehensweise ist im Artikel Radixsort beschrieben und ist eine Form des MSD Radixsort.

Der Speicherbedarf liegt in .

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. s. #Mehlhorn.
    Aber auch eine erschöpfende Rechnung
    Partitio-
    nenzahl
    Anzahl
    Vergleiche
    2 2 0,5000 0,25000
    3 3 0,9630 0,32099
    4 5 1,4167 0,35417
    5 7 1,8675 0,37349
    6 11 2,3169 0,38616
    7 15 2,7657 0,39510
    8 22 3,2140 0,40175
    9 30 3,6620 0,40689
    10 42 4,1098 0,41098
    11 56 4,5575 0,41432
    12 77 5,0051 0,41709
    13 101 5,4526 0,41943
    14 135 5,9000 0,42143
    15 176 6,3474 0,42316
    16 231 6,7947 0,42467
    17 297 7,2420 0,42600
    18 385 7,6893 0,42718
    19 490 8,1366 0,42824
    20 627 8,5838 0,42919
    21 792 9,0310 0,43005
    22 1002 9,4782 0,43083
    23 1255 9,9254 0,43154
    24 1575 10,373 0,43219
    25 1958 10,820 0,43279
    26 2436 11,267 0,43334
    27 3010 11,714 0,43386
    28 3718 12,161 0,43433
    29 4565 12,608 0,43477
    30 5604 13,056 0,43518
    31 6842 13,503 0,43557
    32 8349 13,950 0,43593
    33 10143 14,397 0,43627

    über alle Permutationen zeigt, dass bis zu einer Elementeanzahl von im Mittel weniger als Vergleiche zum vollständigen Sortieren erforderlich sind.