Kurs:Algorithmen und Datenstrukturen/Vorlesung/Sortieren2 Nicht vergleichsbasiertes Sortieren

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Bucket Sort

Auf dieser Seite wird der Sortieralgorithmus BucketSort behandelt.

Idee

Die Elemente kommen aus einem vorher festgelegtem Bereich, z.B. [1...K] für eine natürliche Zahl K und sie sind in [1...K] ungefähr gleich verteilt. Als Eingabe haben wir n Elemente und eine Funktion f die auf den Wertebereich [0,1) abbildet. f(e) ist dann der Sortierschlüssel der Elemente e. Vereinfacht haben wir als Eingabe n Elemente aus dem Wertebereich [0,1), das heißt wir nehmen die Anwendung von Funktion f bereits an. Es wird eine n verkettete Liste erzeugt (buckets), die das Intervall [0,1) in n Teilintervalle der Größe 1/n einteilen. Das bedeutet die Wertebereiche werden in n gleich große Teilintervalle zerlegt. Als nächstes wird jedes Element in die passende Liste eingefügt und danach werden die Listen verkettet. Wir nehmen an, dass die Funktion f eine Eingabe aus n Zahlen in n reellen Zahlen im Bereich [0,1)abbildet. Die Vereinfachte Variante ist, dass die Eingabe der n reellen Zahlen aus dem Bereich [0,1) stammt. Die Aufteilung in Buckets erfolgt dadurch, dass Element e ( $e\in [0,1)$) in Bucket $e\cdot n$ kommt.

Beispiel 1

Als Eingabe haben wir 10 Zahlen (n=10)

Das Element e kommt in Bucket $e\cdot n$. Das Bucket i ($0\leq i<n$) enthält Werte in $[i/n,(i+1)/n)$. Für den Fall mit n=10 kommt das Element e in Bucket $e\cdot 10$. Beispielsweise 0,17 in 1. Das Bucket i enthält Werte in $[i/10,(i+1)/10)$, z.B. i=1:[1/10,2/20)

Beispiel 2

Als weiteres Beispiel ist K=100. Weiterhin haben wir als Eingabe folgende Folge: $[23,54,2,12,65,34,39,94,89,52]$. Sortiert man die Zahlen nun in die Buckets ein, sind die Zahlen danach folgend eingeordnet.

0-9	2
10-19	12
20-29	23
30-39	34	39
40-49
50-59	54	52
60-69	65
70-79
80-89	89
90-99	94

Von links nach rechts sind es verkettete Listen. Auf die einzelne Buckets, die mehr als ein Element besitzen, muss im Anschluss eventuell noch ein vergleichbasiertes Sortierverfahren angewandt werden. Wie es in diesem Beispiel beim Bucket von 50-59 der Fall ist.

Anschließend erhalten wir als Ausgabe: $[2,12,23,34,39,52,54,65,89,94]$.

Algorithmus

void bucketSort(int[] f, int bound){
   int n = f.length;
   List<List<Integer>> buckets = createBuckets(n);
   for(int i = 0; i < n; i++)
      buckets.get(n*f[i]/bound).add(f[i]);
   int idx = 0;
   for(int i = 0; i < n; i++){
      quickSort(buckets.get(i));
      for(int j = 0; j < buckets.get(i).size(); j++)
         f[idx++] = buckets.get(i).get(j);
   }
}
List<List<Integer>> createBuckets(int n){
   List<List<Integer>> buckets 
      = new ArrayList<List<Integer>>();
   for(int i = 0; i < n; i++)
      buckets.add(new ArrayList<Integer>());
   return buckets;
}

Analyse

Theorem der Terminierung

Der Algorithmus BucketSort terminiert für jede Eingabe int[] f nach endlicher Zeit.

Beweis

Alle Schleifenvariablen haben wohl-definierte Start- und Endpunkte.

Theorem der Korrektheit

Das Theorem der Korrektheit besagt, dass nach Aufruf BucketSort(f,bound) f ein sortiertes Array mit gleichen Elementen wie vor dem Aufruf ist.

Beweis

Sei i<j beliebig und betrachte f[i] und f[j] nach Anwendung BucketSort(f, bound). Falls n*f[i]/bound = n*f[j]/bound so  sind f[i] und f[j] im selben Bucket gelandet. Nach Annahme ist QuickSort korrekt und hat den Bucket korrekt sortiert.  Anschließend wurde zunächst f[i] und dann f[j] in das Array f geschrieben, also folgt f[i] ≤ f[j]. Fall n*f[i]/bound  ̸=    n*f[j]/bound so muss n*f[i]/bound < n*f[j]/bound gelten  (da i<j), daraus folgt direkt f[i] < f[j]. Also ist f sortiert. 

Theorem der Laufzeit

Das Theorem der Laufzeit besagt, ist f mit n=f‐length ein Array mit Elementen, die gleich verteilt  sind in [1..bound] so hat BucketSort(f, bound) eine Laufzeit von $\Theta (n)$.

Beweis

Im Schnitt landet in jedes Bucket genau ein Element (da  Gleichverteilung) und die Anwendung des  Sortieralgorithmus auf jedes Bucket (und die innerste  for‐Schleife) kann vernachlässigt werden. Alle anderen  Schleifen haben genau n Durchläufe, also $\Theta (n)$.  Falls die Annahme der Gleichverteilung nicht gilt,  wird keine lineare Komplexität erreicht. 

Aufwandsanalyse

Die zugrunde liegende Annahme ist, dass die Eingabe-Elemente gleich verteilt auf [0,1) sind und wir somit eine uniforme Eingabeverteilung haben. Bzw. im Allgemeinfall ist f(e) gleich verteilt auf [0,1) Im Algorithmus werden n Elemente eingefügt und InsertionSort mit $m_{1},...,m_{n}$ wird aufgerufen, wobei $m_{i}$ die Anzahl der Elemente in Bucket i ist. $T(n)=O(n)+\sum _{i=0}^{n-1}O(m_{i}^{2})$

Bei gleich verteilter Eingabe liegt O(n) vor. Die Abschätzung ist intuitiv, da wir n Elemente auf n Buckets verteilen! Wir erwarteten 1 Elemente je Bucket(genauer: O(1) – d.h. konstant). Das Sortieren (z.B. InsertionSort) je Bucket ist dann O(1). Da wir n buckets haben, muss n-mal sortiert werden. Falls die Annahme der Gleichverteilung nicht gilt, wird keine lineare Komplexität erreicht.