Bucketsort

Bucketsort (von {{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}} „Eimer“) 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.

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 halboffene Intervall <math>[0,1[</math> 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 höchsten Signifikanz nehmen. Während der Sortierung verwendet der Algorithmus <math>k</math> „Buckets“, die in einem Array angeordnet sind. Die Verteilung der Elemente geschieht über dieses Array, indem jedes Element <math>e</math> in den {{#if:trim|<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 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 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-Laufzeit angesehen.<ref>s. #Mehlhorn.
Aber auch eine erschöpfende Rechnung

<math>n</math>	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 Permutationen 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

• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|9783540779773}}

| {{bibISBN/{{#invoke:URIutil|plainISBN|9783540779773}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|9783540779773}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} 5.6 Breaking the Lower Bound

• {{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0262032937}}

| {{bibISBN/{{#invoke:URIutil|plainISBN|0262032937}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0262032937}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 174
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}}

• {{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}

| {{bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 169
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}}

• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}