close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Kapitel 8 Fortgeschrittene Sortieralgorithmen

EinbettenHerunterladen
Technische Universität München
Technische Universität München
Kapitel 8 Fortgeschrittene Sortieralgorithmen
Zur Erinnerung: in Kapitel 6 Elementare Sortierverfahren
• Sortierverfahren, die auf Vergleichen von Werten basieren.
• Aufwand zum Sortieren von Feldern von n Elementen, bislang:
• Sortieren durch Einfügen, in-place, O(n2)
• Sortieren durch Mischen, nicht in-place, O(n log n)
• Quicksort, in-place, mit O(n2), aber Worst-Case nur selten
Frage1: Gibt es in-place Sortierverfahren mit O(n log n)
Antwort: ja, Heap-Sort
Frage2: Gibt es vergleichendes Sortierverfahren, das um mehr
als einen Faktor c schneller ist als Merge- oder Heap-Sort?
Antwort: Nein, die beiden sind asymptotisch optimal
1
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
8.1 Heapsort (Floyd 1964)
Idee
Notwendig: Einführung einer zusätzlichen Datenstruktur, des Heap,
zur Verwaltung der Informationen während der Laufzeit des
Algorithmus Heapsort.
Bem. 1: Eine Heap-Datenstruktur wird auch in anderen Kontexten
häufig verwendet, z.B. bei der Speicherverwaltung, um
dynamisch erzeugte Objekte zu speichern (u.a. Java), um Garbage
Collection zu implementieren, etc.
Bem. 2: Eine Heap-Struktur wird auch häufig verwendet, um eine
effiziente Prioritätenwarteschlange zu implementieren.
2
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Technische Universität München
Technische Universität München
Beispiel für einen Max-Heap
Definition
Ein Heap ist ein fast vollständiger Binärbaum für den gilt:
• Alle inneren Knoten bis auf maximal einen haben genau
zwei Kinder.
• Alle Knoten mit weniger als zwei Kindern befinden sich
auf der untersten oder zweituntersten Schicht.
• Die unterste Schicht (Blätter) ist von links nach rechts aufgefüllt.
• Jedem Knoten wird ein Datensatz zugeordnet.
9
8
7
Man unterscheidet 2 Klassen von Heaps: Max-Heap und Min-Heap
Definition Max-Heap-Eigenschaft:
Für jeden Knoten außer der Wurzel gilt, dass sein Schlüssel kleiner
ist als der seines Vater-Knotens. (Min-Heap-Eigenschaft: analog)
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
5
3
3
1
6
2
4
0
Darstellung des Heap als lineares Feld A[i]
i
1 2 3 4 5 6 7 8 9 10
A[i] 9 8 5 7 1 2 4 3 6 0
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
4
Technische Universität München
Technische Universität München
Für Heapsort werden Max-Heap-Strukturen verwendet.
8.1.1 Max-Heap Baumstruktur
• Höhe eines Heaps ist die Höhe der Wurzel des Baums.
• Für einen Heap von n-Elementen gilt: Höhe ist O(log2 n) (Binärbaum)
• Die Operationen auf einem Heap haben eine Laufzeit, die
höchstens proportional zur Höhe des Heaps ist, also O(log2 n).
Grundlegende Operationen auf einem Heap:
• Operation Max-Heapify, Laufzeit ist O(log2 n), sorgt für die
Aufrechterhaltung der Heap-Eigenschaft.
• Operation Build-Max-Heap, Laufzeit ist O(n), erzeugt einen
Max-Heap aus einem ungeordnetem Eingabefeld.
5
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
• Operation Heapsort, Laufzeit ist O(n log2 n), sortiert ein Feld in-place.
• Operationen Max-Heap-Insert, Heap-Extract-Max,
Heap-Increase-Key, Heap-Maximum: Laufzeit jeweils O(log2 n),
Verwendung des Heaps als Prioritätenwarteschlange.
8.1.2 Operation Max-Heapify
Operation zur Aufrechterhaltung der Heap-Eigenschaft
• Eingabe: Feld A, Index i
• Left(i) berechnet für einen gegebenen Knoten i den Index j seines
linken Sohnes: Left(i) = 2i
• Right(i) berechnet für Knoten i den Index j seines rechten Sohnes:
Right(i) = 2i+1
Technische Universität München
Technische Universität München
• Left(i) und Right(i) sind Indizes von Wurzeln von Max-Heaps, aber
• A[i] kann ggf kleiner als seine Kinder sein: in diesem Fall wäre die
Heap-Eigenschaft verletzt!
Max-Heapify:
Idee des Alg.:
Wert von A[i]
sinkt ‚nach unten‘,
damit der Teilbaum
mit Wurzel i wieder
ein Max-Heap ist.
MAX-HEAPIFY (A, i)
1. l = LEFT (i)
2. r = RIGHT (i)
3. if l ≤ heap-größe [A] und A[l] > A[i]
4.
then maximum = l
5.
else maximum = i
6. if r ≤ heap-größe [A] und A[r] > A [maximum]
7. then maximum = r
8. if maximum ≠ i
9. then vertausche A[i] ↔A [maximum]
10.
MAX-HEAPIFY (A, maximum)
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
6
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
7
Beispiel: Max-Heapify(A, 2), heap-größe[A] = 10
(a) A[2] verletzt die Max-Heap
Eigenschaft
(b) Nach Vertauschen von A[2] und A[4]:
A[2] erfüllt Heap-Eigenschaft,
aber Heap-Eigenschaft ist nun für
A[4] zerstört: rekursiver Aufruf mit i=4
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
8
Technische Universität München
Technische Universität München
Beispiel (Forts.): Max-Heapify(A, 2), heap-größe[A] = 10
(c) Nach Vertauschen von A[4] und A[9]:
A[4] erfüllt Heap-Eigenschaft,
rekursiver Aufruf mit i=9
führt zu keiner Änderung der
Datenstruktur: Terminierung
Erläuterungen zur Analyse von Max-Heapify
• Max-Heapify für Teilbaum mit Wurzel i und Knotennummern bis n
• Knoten mit laufender Nummer i hat die Tiefe d(i) = ⌊ log2(i) ⌋
• Max-Heapify maximal bis Blatt mit Tiefe d = ⌊ log2 (n) ⌋
• Jede zusätzliche Entscheidungsstufe erfordert 2 Vergleiche.
Tiefe 0
Tiefe 1
Laufzeit von Max-Heapify für Teilbaum der Größe n:
• Bestimmung der Beziehung zw. A[i], A[Left(i)], A[Right(i)]: O(1)
• Ausführung von Max-Heapify auf Teilbaum eines der Kinder:
• Teilbäume der Kinder: max Größe 2n/3
T(n) ≤ T(2n/3) + O(1) = O(log2 n)
9
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Tiefe 2
Tiefe 3
10
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Technische Universität München
Technische Universität München
Maximale Anzahl von Vergleichen beim Aufruf von Max-Heapify
für Teilbaum mit Wurzel i und Knotennummern bis n
8.1.3 Operation Build-Max-Heap
Operation zur Konstruktion eines Heaps
BUILD-MAX-HEAP (A)
• Eingabe: Feld A[1..n],
1. heap-größe [A] = länge [A]
n = länge(A)
2. for i = länge [A] /2 downto 1
3.
i
 log(i)
 log(n)
Anzahl der Vergleiche: 2· ( ⌊ log(n) ⌋ - ⌊ log(i) ⌋ )
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
do MAX-HEAPIFY (A,i)
Korrektheit?
Schleifeninvariante: Zu Beginn jeder Iteration der for-Schleife ist
jeder Knoten i + 1, i + 2, …, n die Wurzel eines Max-Heaps.
Korrektheitsbeweis:
Initialisierung: Erste Iteration der for-Schleife: i=  n/2  .
Jeder Knoten  n/2  +1,  n/2  +2, ..n ist ein Blatt,
d.h. Baum besitzt nur die Wurzel, Max-Heap-Eigenschaft ist erfüllt.
11
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
12
Technische Universität München
Technische Universität München
Korrektheitsbeweis: (Forts.)
Weitere Iterationen: Für Kind-Knoten von i gilt:
Index des Kind-Knotens > i,
Wir gehen davon aus, dass die Schleifeninvariante gilt, dann gilt:
Beide Kind-Knoten von i sind Wurzeln von Max-Heaps.
Damit ist die Vorbedingung für den Aufruf von Max-Heapify(A, i)
erfüllt.
Beispiel: Feld mit 10 Elementen und
zugehöriger Binärbaum
Terminierung: i = 0, Schleifeninvariante gilt; damit gilt, dass
jeder Knoten 1, 2, 3, ..., n eine Wurzel eines Max-Heaps ist. D.h.
insbesondere ist der Knoten mit Index 1 die Wurzel eines
Max-Heaps und damit ist der ganze Binärbaum ein Max-Heap.
(b) Nach Beendigung des Aufrufs,
i = 4, Aufruf von
Max-Heapify(A, i)
(a) Schleifenvariable i = 5,
Zeile 3 vor Aufruf von
Max-Heapify(A, i)
13
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
14
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Technische Universität München
Technische Universität München
Beispiel (Forts.):
(c) – (e) Iterationen der for-Schleife in Build-Max-Heap
(f) Max-Heap nach Terminierung von Build-Max-Heap.
Laufzeit von Build-Max-Heap
• Jeder Aufruf von Max-Heapify erfordert O(log2 n) Schritte
• Es gibt O(n) Max-Heapify-Aufrufe. D.h.
• Tbuild-max-heap(n) = O(n log2 n). Das ist eine obere Schranke für
die Laufzeit. Diese Schranke ist korrekt, aber nicht sehr scharf.
Man kann zeigen, dass die Laufzeit von Max-Heapify(A, i) von
der Höhe des Knotens mit Index i abhängt. Da die Höhe der
meisten Knoten klein ist (das kann man beweisen), kann man
beweisen (siehe Cormen S. 132), dass gilt:
Tbuild-max-heap(n) = O(n). D.h. zur Berechnung eines
Max-Heaps aus einem unsortiertem Feld benötigt man Lineare Zeit.
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
15
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
16
Technische Universität München
Technische Universität München
8.1.4 Put it all together: der Heapsort-Algorithmus
• Eingabe: Feld A[1..n]
n = länge(A)
• Zeile 1:
Nach Terminierung von
Build-Max-Heap(A):
maximales Element ist
in A[1] gespeichert.
HEAPSORT (A)
1. BUILD-MAX-HEAP (A)
2. for i = länge [A] downto 2
3.
do vertausche A [1] ↔ A[i]
4.
heap-größe [A] = heap-größe [A] -1
5
MAX-HEAPIFY (A,1)
Beispiel (Forts.)
(b) – (j):
Max-Heaps
nach Zeile 5
(k) Ergebnis:
Sortiertes Feld
Beispiel:
(a) Situation in Zeile 2
17
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Technische Universität München
Technische Universität München
Laufzeit von Heapsort
• Aufruf von Build-Max-Heap: O(n)
• n – 1 Aufrufe von Max-Heapify: O(log2 n)
• Gesamtlaufzeit: Theapsort(n) = O(n log2 n)
• Man kann sogar zeigen: Heapsort kann ein Feld der Länge n mit
höchstens 2n log2 (n) + 7/2 n Vergleichen sortieren.
Analyse der Speicherplatzanforderungen:
• Heapsort benötigt nur den Speicherplatz für die zu
sortierenden Daten.
• Lediglich 4 zusätzliche Variablen (Speicherplätze) werden
benötigt.
• Heapsort arbeitet in-place (man nennt das auch in-situ).
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
18
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
19
HeapSort in der Programmiersprache C
int heapsort( int * data, int n ) // zu sortierendes Feld und seine Länge
{
const int WIDTH= 8;
// Anzahl der Kinder pro Knoten
int val, parent, child, w, max, i;
int m= (n + (WIDTH - 2)) / WIDTH; // erstes Blatt im Baum
int count= 0;
// Zähler für Anzahl der Vergleiche
while ( 1 )
{
if ( m ) {
parent= --m;
val= data[parent];
}
else
if ( --n ) {
val= data[n];
data[n]= data[0];
parent= 0;
}
else
break;
// Teil 1: Konstruktion des Heaps
// zu versickernder Wert
// Teil 2: eigentliche Sortierung
// zu versickernder Wert vom Heap-Ende
// Spitze des Heaps hinter den Heap in
// den sortierten Bereich verschieben
// Heap ist leer; Sortierung beendet
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
20
Technische Universität München
Technische Universität München
HeapSort in der Programmiersprache C
8.2 Prioritäts-Warteschlange
Motivation: Heap-Konzept zur Organisation von Datenstrukturen
Ziel: Sehr effiziente Such-Operationen auf speziell vorsortierten
Datenstrukturen: sortiert nach Priorität in einer Warteschlange.
Ansatz: Um eine solche Warteschlange effizient aufzubauen und zu
verwalten, verwendet man häufig eine Heap-Datenstruktur.
Besonderheit: In einer Prio-Warteschlange können Elemente verwaltet werden, deren Werte sich dynamisch ändern (z.B. Prio erhöhen)
Definition
Eine Prioritäts-Warteschlange ist eine Datenstruktur für die Speicherung einer Menge S von Datenelementen, denen jeweils ein Wert,
der Schlüssel, zugeordnet ist.
while ( (child= parent * WIDTH + 1) < n ) // erstes Kind;
{
// Abbruch am Ende des Heaps
w= n - child < WIDTH ?
n - child : WIDTH;
// Anzahl der vorhandenen Geschwister
count += w;
for ( max= 0, i= 1; i < w; ++i )
// größtes Kind suchen
if ( data[child+i] > data[child+max] )
max= i;
child += max;
if ( data[child] <= val )
// kein Kind mehr größer als der
break;
// zu versickernde Wert
data[parent]= data[child]; // größtes Kind nach oben rücken
parent= child;
// in der Ebene darunter weitersuchen
}
data[parent]= val;
}
return count;
// versickerten Wert eintragen
}
21
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Technische Universität München
Technische Universität München
Operationen auf Prioritätswarteschlangen: Basis ist ein Max_Heap
• Insert(S, x): Einfügen eines Datenelementes in die
Prioritätswarteschlange
• Maximum(S): gibt das Element von S mit dem größten
Schlüssel zurück
• Extract_Max: entfernt das Element mit dem größten Schlüssel
aus S und gibt das Element aus
• Increase-Key(S, x ,k): erhöht den Wert des Schlüssels von
Element x auf den neuen Wert k, k ≥ x
Anwendung für Prioritätswarteschlangen: u.a.
• Scheduling von Simulationsjobs (event-driven simulation)
• Programm mit höchster Priorität wird gestartet (CPU-Scheduling)
• Business Class Check-In am Flughafen
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
22
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
23
Implementierung der Operationen in Pseudo-Code:
(1) Implementierung der Operation Maximum in O(1)
HEAP-MAXIMUM(A)
return(A[1])
Beispiel-Baum
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
24
Technische Universität München
Technische Universität München
Implementierung der Operationen in Pseudo-Code: (Forts.)
(2) Implementierung der Operation Extract-Max in O(lgn).
HEAP-EXTRACT-MAX (A)
1. if n < 1
2.
then error „Heap-Unterlauf“
3. max = A[1]
4. A[1] = A[n]
5. n
=n–1
6. MAX-HEAPIFY (A, 1)
7. return max
Implementierung der Operationen in Pseudo-Code (Forts.)
(3) Implementierung der Operation Increase-Key in O(log2 n)
HEAP-INCREASE-KEY (A, i, schlüssel)
1. if schlüssel < A[i]
2.
then error “neuer Schlüssel ist kleiner als der aktuelle Schlüssel”
3. A[i] = schlüssel
4. while i > 1 und A[Vater(i)] < A[i]
5.
do vertausche A[i] ↔ A[Vater(i)]
6.
i = Vater(i)
sei heap-größe[A] = n
25
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Technische Universität München
Implementierung der Operationen in Pseudo-Code (Forts.)
(4) Implementierung der Operation Insert in O(log2 n).
MAX-HEAP-INSERT (A, schlüssel)
1. n = n + 1
2. A [n] = − ∞
3. HEAP-INCREASE-Key (A, n, schlüssel)
Fazit :
• Unter Nutzung der Datenstruktur Heap ist es möglich, jede
Operation auf einer Prioritätenwarteschlange mit n Elementen
in einer Laufzeit von O(log2 n) durchzuführen.
• Der Heap ist eine sehr effiziente Datenstruktur für eine
Vielzahl von Anwendungen.
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
26
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Technische Universität München
8.3 Vergleichsbasiertes Sortieren
Frage: Kann man eine untere Schranke Ω für das vergleichsbasierte
Sortieren angeben?
Antwort: ja, man kann zeigen, dass vergleichende Sortierverfahren
im schlechtesten Fall Ω(n log n) Vergleiche benötigen.
Beweisidee:
• Seien n Eingabewerte in einem Feld A gegeben
• Vergleichende Sortierverfahren können als Entscheidungsbäume
interpretiert werden.
Definition: Ein Entscheidungsbaum ist ein vollständiger Binärbaum,
der die Vergleiche zwischen den Elementen repräsentiert.
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
28
Technische Universität München
Technische Universität München
Entscheidungsbaum:
• Sei n die Anzahl der Eingaben, also a1, …, an
• jeder innere Knoten wird mit i:j annotiert, mit i, j ≤ n
• i:j steht für den Vergleich ai ≤ aj
• der linke Teilbaum des Knotens beschreibt die Vergleiche, wenn
gilt ai ≤ aj
• der rechte Teilbaum des Knotens beschreibt die Vergleiche,
wenn gilt ai > aj
• jedes Blatt des Entscheidungsbaums wird mit einer Permutation
der Eingabewerte annotiert, d.h. der Entscheidungsbaum ‚zählt‘
alle Permutationen auf.
• Für n Eingaben gilt: es gibt n! Permutationen der Eingaben
29
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Beispiel: Entscheidungsbaum für Sortieren mit Einfügen
• Eingabe: 3-elementiges Feld A= (6, 8, 5)
• 3! = 6 verschiedene Permutationen der Eingabefolge sind möglich,
d.h. Entscheidungsbaum hat mind. 6 Blätter .
Sortiertes Feld:
A= (5, 6, 8)
Technische Universität München
Technische Universität München
Zusammenhang: Entscheidungsbaum und Sortieralgorithmus
• Eine Ausführung des Sortieralgorithmus A entspricht einem
Pfad von der Wurzel des Baums bis zu einem erreichbaren Blatt.
D.h. durch die Ausführung wird eine sortierte Permutation erzeugt.
• Notwendige Bedingung für die Korrektheit eines vergleichsbasierten
Sortieralgorithmus A ist: der Algorithmus erzeugt alle möglichen n!
Permutationen bei n Eingabewerten; der Entscheidungsbaum hat
n! Blätter.
• Jedes Blatt muss über einen Pfad von der Wurzel aus erreichbar
sein, der einer Ausführung von A entspricht (erreichbares Blatt).
• Für ein Blattknoten der Tiefe d sind d Vergleiche zum Sortieren
erforderlich.
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
30
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
31
Aus dem vorher Gesagten folgt:
• Für vergleichsbasierte Sortieralgorithmen gilt im schlechtesten Fall:
Die Höhe seines Entscheidungsbaums = Anzahl der Vergleiche
D.h. Eine untere Schranke für die Höhen aller Entscheidungsbäume,
in denen jede Permutation als erreichbares Blatt auftritt, ist eine untere
Schranke für die Laufzeit jedes vergleichenden Sortieralgorithmus.
Satz:
Für jeden vergleichenden Sortieralgorithmus sind im Worst-Case
Ω(n log n) Vergleichsoperationen erforderlich.
Der Omega-Operator Ω bezeichnet eine untere Schranke, es gilt:
Ω(g(n))= { f(n): es existieren Konstanten c, n0, so dass
0 ≤ cg(n) ≤ f(n) für alle n ≥ n0 }
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
32
Technische Universität München
Technische Universität München
Beweis
• zu bestimmen ist die Höhe eine Entscheidungsbaums, in dem
jede Permutation als Blatt auftritt
• Sei ein Baum, der einem Sortieralgorithmus für n Elemente
entspricht, gegeben, mit der Höhe h und mit r erreichbaren Blättern.
• jede Permutation entspricht einem Blatt, d.h. es gilt: n! ≤ r.
• Da ein Binärbaum der Höhe h nicht mehr als 2h Blätter hat, gilt:
n! ≤ r ≤ 2h
d.h. Durch Anwendung von Log gilt : h ≥ lg(n!)
Zudem gilt: lg(n!) = Θ(n lg n) wg
Also gilt: h = Ω(n lg n)
Korollar: Merge-Sort und Heap-Sort sind asymptotisch optimale
vergleichende Sortierverfahren.
33
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
8.4 Sortieren in Linearzeit
Hier: Beispiel Bucketsort
• Bucketsort arbeitet nicht vergleichend, so dass die untere Schranke
Ω(n log n) nicht gilt.
• Bucketsort arbeitet in linearer Zeit, wenn die Eingabewerte
unabhängig und gleich verteilt über das Intervall [0, 1) vorliegen,
Idee
• Intervall [0, 1) wird in n gleich große Teilintervalle (Buckets) aufgeteilt
• n Eingabewerte werden auf die Teilintervalle verteilt.
• Sortieren der Zahlen in jeden Bucket.
• Auflisten aller Zahlen aller Buckets gibt die sortierte Folge.
Technische Universität München
Technische Universität München
Eingabe: Feld A der Länge n, 0 ≤ A[i] < 1 für jedes Feldelement A[i]
Bucketsort benötigt ein Hilfs-Feld B[0 .. n – 1] von verketteten Listen
BUCKET-SORT (A)
1 n = länge [A]
2 for i = 1 to n do
3
füge A[i] in die Liste B[nA [i]] ein
4 for i = 0 to n − 1 do
5
sortiere die Liste B[i] durch Sortieren durch Einfügen
6 Hänge die Listen B[0], B[1], …., B[n − 1] in dieser Reihenfolge hintereinander
Beispiel: Eingabefeld A[1 .. 10]
• B[0 .. 9] nach Ausführung von
Zeile 5
• Bucket i enthält Zahlen aus dem
Intervall [i/10, (i+1)/10)
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
34
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
Bucketsort: intuitive Erläuterung
• Gegeben seien zwei Elemente A[i] und A[j], oBdA: A[i] ≤ A[j].
• A[i] und A[j] sind entweder im gleichen Bucket eingeordnet oder A[i]
befindet sich in einem Bucket mit kleinerem Index als der von A[j].
• Fall1: A[i] und A[j] liegen im gleichen Bucket, dann werden sie
durch die Anweisungen in den Zeilen 4-5 sortiert.
• Fall2: A[i] und A[j] liegen in verschiedenen Buckets, dann werden
sie durch die Anweisung in der Zeile 6 sortiert.
Laufzeitanalyse von Bucketsort:
• alle Zeilen, außer Zeile 5, erfordern im Worts-Case O(n)-Schritte
• Zeile 5: Sortieren durch Einfügen, d.h.
Bestimmen der Laufzeit von n Aufrufen von Insertion-Sort.
35
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
36
Technische Universität München
Technische Universität München
Insertion-Sort erfordert quadratische Laufzeit O(n2).
Sei ni die Zufallsvariable, die die Anzahl der Elemente im
Bucket B[i] beschreibt. Damit können wir die Laufzeit von Bucketsort
beschreiben durch:
Man kann zeigen, dass gilt: (siehe Cormen)
Damit erhält man als erwartete Laufzeit von Bucketsort:
Θ(n) + n * O(2 – 1/n) = Θ(n)
Bestimmen der Laufzeit im Mittel, gleichverteilte Werte liegen zugrunde.
Durch Bilden der Erwartungswerte
erhalten wir:
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
37
D.h. die erwartete Laufzeit von Bucketsort ist linear.
Fazit:
• Bucketsort ist sehr schnell,
• benötigt aber zusätzlichen Speicher (out-of-place) und der
• Wertebereich der zu sortierenden Zahlen muss begrenzt sein.
• Zudem müssen die Werte unabhängig und gleich verteilt sein.
AuD, WS10/11, C. Eckert, Kapitel 8 Fortgeschrittene Sortierverfahren
38
Autor
Document
Kategorie
Uncategorized
Seitenansichten
1
Dateigröße
269 KB
Tags
1/--Seiten
melden