Bucketsort - LinkFang.de





Bucketsort


Bucketsort (von engl. 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 Insertionsort sortiert.
  3. Der Inhalt der sortierten Buckets wird konkateniert.

Das Verfahren arbeitet also out-of-place.

Algorithmus

Die Eingabe von Bucketsort ist eine Liste [math]l[/math] mit [math]n[/math] Elementen und eine Funktion [math]f[/math], die jedes Element der Liste in das Intervall [math][0,1][/math] abbildet. Die Ausgabe ist eine sortierte Liste, wobei [math]f(e)[/math] den Sortierschlüssel von einem Element [math]e[/math] berechnet. Während der Sortierung verwendet der Algorithmus [math]n[/math] „Buckets“, die in einem Array angeordnet sind. Die Verteilung der Elemente geschieht über dieses Array, indem jedes Element [math]e[/math] in den [math]\lfloor f(e)\cdot n\rfloor[/math]-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)
   return r

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

Komplexität

Die Verteilung der Funktionswerte von [math]f[/math] bestimmt die Laufzeit von Bucketsort. Die Laufzeit ist in [math]\mathcal{O}(n) + \sum_{i=0}^{n-1} \mathcal{O}(l_i^2)[/math] (in O-Notation), wobei [math]l_i[/math] die Anzahl der Elemente im [math]i[/math]-ten Bucket bezeichnet. Bei einer Gleichverteilung ist die Gesamtlaufzeit [math]\mathcal{O}(n)[/math], da auch die Summe der Quadrate der Bucketgrößen linear ist. Intuitiv ist dies direkt einsehbar, da bei einer Gleichverteilung von [math]n[/math] Elementen auf [math]n[/math] Buckets jeder Bucket im Erwartungsfall eine konstante Anzahl von Elementen enthält und damit eine Sortierkomplexität von [math]\mathcal{O}(1)[/math] erzeugt. Die effiziente Laufzeit von [math]\mathcal{O}(n)[/math] ist nicht nur bei einer Gleichverteilung gegeben, sondern bei allen Verteilungen, nach denen der Summenterm asymptotisch linear ist.

Bei anderen Werte-Verteilungen wird die Laufzeit des Bucketsortalgorithmus von der Laufzeit des Sortier-Algorithmus dominiert, der zur Sortierung eines Buckets verwendet wird. Ein solcher Worst-Case tritt ein, wenn beispielsweise alle Elemente zu genau einem Bucket zugeordnet werden. Bei Verwendung von Insertion-Sort für die Sortierung der Buckets wäre die Gesamtlaufzeit damit in [math]\mathcal{O}(n^2)[/math].

Falls die Werte bei jedem Bucketsort-Aufruf bzw. über alle Aufrufe hinweg entsprechend verteilt sind, ist die effiziente Laufzeit von [math]\mathcal{O}(n)[/math] eine Worst-Case- bzw. Average-Case-Laufzeit.

Der Speicherbedarf liegt in [math]\mathcal{O}(n)[/math].

Literatur

Siehe auch


Kategorien: Sortieralgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Bucketsort (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.