imported>Bartleby08 am 27. Juli 2025 um 14:00 Uhr

2025-07-27T14:00:30Z

Neue Seite

'''Bucketsort''' (von {{enS|bucket}} „[[Eimer]]“) ist ein [[Sortierverfahren]], das für bestimmte [[Wahrscheinlichkeitsverteilung|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 [[Mergesort]] sortiert.
# Der Inhalt der sortierten Buckets wird [[Konkatenation (Listen)|konkateniert]].

Das Verfahren arbeitet also [[Out-of-place-Algorithmus|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 [[Halboffenes Intervall#Halboffenes (genauer rechtsoffenes) Intervall|halboffene Intervall]] <math>[0,1[</math> [[Monotone reelle Funktion|monoton]] in der Weise abbildet, dass <math>f(e)\le f(e^\prime)</math> für <math>e</math> sortiermäßig <math>\prec e^\prime</math>. Basiert die Sortierreihenfolge <math>\prec</math> auf einem Vergleich binärer Daten, kann man die Bits mit der [[Bitwertigkeit|höchsten Signifikanz]] nehmen. Während der Sortierung verwendet der Algorithmus <math>k</math> „Buckets“, die in einem [[Array (Datentyp)|Array]] angeordnet sind. Die Verteilung der Elemente geschieht über dieses Array, indem jedes Element <math>e</math> in den {{nowrap|<math>\lfloor f(e)\cdot k\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:

<syntaxhighlight lang="c">
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
</syntaxhighlight>

Der Algorithmus sortiert [[Stabilität (Sortierverfahren)|stabil]], wenn der für die Sortierung der Buckets verwendete Sortier-Algorithmus, hier mergesort, 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}^{k-1} \mathcal{O}(l_i \log l_i)</math> (in [[Landau-Symbole|O-Notation]]), wobei <math>l_i</math> die Anzahl der Elemente im <math>i</math>-ten Bucket bezeichnet. Bei einer [[Gleichverteilung]] ist die Gesamtlaufzeit in <math>\mathcal{O}(n)</math>, 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 <math>\mathcal{O}(n)</math> ist nicht nur bei einer Gleichverteilung gegeben, sondern bei allen Verteilungen, nach denen der Summenterm [[asymptotisch]] linear ist. Sie wird auch als [[Average Case|Average-Case]]-Laufzeit angesehen.<ref>s. [[#Mehlhorn]]. 
Aber auch eine erschöpfende Rechnung
{| class="wikitable" style="text-align:right"
|-
!<math>n</math>!![[Partitionsfunktion|Partitio- nenzahl]]!!<math>\emptyset</math> Anzahl Vergleiche!!<math>\emptyset / n</math>
|-
|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 [[Permutation]]en zeigt, dass bis zu einer Elementeanzahl von <math>n \le 33</math> im Mittel weniger als <math>n/2</math> Vergleiche zum vollständigen Sortieren erforderlich sind.</ref>

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 <math>\mathcal{O}(n \log n)</math>.

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 <math>\mathcal{O}(n)</math>.

== Siehe auch ==
* [[Hybridsort]], ein Sortierverfahren, das die Eigenschaften von Bucketsort und [[Heapsort]] kombiniert.

== Einzelnachweise ==
<references />

== Literatur ==
* {{Anker|Mehlhorn}}{{BibISBN|9783540779773}} 5.6 Breaking the Lower Bound
* {{BibISBN|0262032937|Seite=174}}
* {{BibISBN|0201896850|Seite=169}}
* {{Literatur |Autor=Apostolos Burnetas und Daniel Solow und Rishi Agarwal |Titel=An analysis and implementation of an efficient in-place bucket sort |Sammelwerk=Acta Informatica |Band=34 |Nummer=9 |Datum=1997 |Seiten=687–700 |Sprache=en |Kommentar=Die Bucketsort-Variante wird als Groupsort bezeichnet |DOI=10.1007/s002360050103}}
* {{Literatur |Autor=E. J. Isaac und R. C. Singleton |Titel=Sorting by Address Calculation |Sammelwerk=Journal of the ACM |Band=3 |Nummer=3 |Datum=1956-07 |Seiten=169–174 |Sprache=en |DOI=10.1145/320831.320834}}

[[Kategorie:Sortieralgorithmus]]

Bucketsort - Versionsgeschichte

imported>Bartleby08 am 27. Juli 2025 um 14:00 Uhr