Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
2.3 Sortieren
2.3.1 Einleitung 2.3.2 Einfache Sortierverfahren 2.3.3 Höhere Sortierverfahren 2.3.4 Komplexität von Sortierverfahren 2.3.5 Spezielle Sortierverfahren
1
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort
• Idee – Divide & Conquer – Wähle ein Element R aus – Teile Folge in zwei Sub-Folgen
RL ≤ R und RR ≥ R – Sortiere RL und RR durch rekursiven Aufruf – Setze Teilfolgen zusammen: RL ⊕ R ⊕ RR
2
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort
3
h k a f i b c d l o n j e g m
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort
4
h k a f i b c d l o n j e g m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort
5
h k a f i b c d l o n j e g m
d g j n i o l h c b f a e k m
h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort
6
h k a f i b c d l o n j e g m
d g j n i o l h c b f a e k m l d
h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort
7
h k a f i b c d l o n j e g m
d g j n i o l h c b f a e k m
b c n l i k j h g e f a d o m
l d
h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort
8
h k a f i b c d l o n j e g m
d g j n i o l h c b f a e k m
b c n l i k j h g e f a d o m
l d
h
n j f b
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort
9
h k a f i b c d l o n j e g m
d g j n i o l h c b f a e k m
a b m l k j i h g f e c d n o
b c n l i k j h g e f a d o m
l d
h
n j f b
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Algorithmus
• QuickSort(A[l..r]) if l < r then m ← Partition(A[l..r]) QuickSort(A[l..m−1]) QuickSort(A[m+1..r])
• Aufruf mit: QuickSort(A[1..n])
10
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Algorithmus
• Partition(A[l..r]) i ← l−1; j ← r while i < j do i ← i+1 while A[ i ] < A[ r ] do i ← i+1 j ← j−1 while A[ j ] > A[ r ] do j ← j−1 swap(A[ i ], A[ j ]) swap(A[ i ], A[ j ]) swap(A[ i ], A[ r ]) return i
11
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Algorithmus
• Achtung: Verwende Sentinel, um korrekte Terminierung der inneren Schleife zu garantieren.
• Aufruf mit A[0] ← − ∞ QuickSort(A[1..n])
• while A[ i ] < A[ r ] do i←i+1
• while A[ j ] > A[ r ] do j←j−1
12
Bricht spätestens für i = r ab
Bricht spätestens für j = l − 1 ab
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
13
k j g a f i b l d c o e n m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
14
k j g a f i b l d c o e n m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
15
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
16
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
17
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
18
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
19
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
20
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
21
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
22
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
23
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
24
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
25
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
26
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
27
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
28
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
29
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
30
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
31
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
32
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
33
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
34
k j g a f i b l d c o e n m h
i
j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
35
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
36
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
37
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
38
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
39
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
40
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
41
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
42
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
43
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
44
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
45
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
46
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
47
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
48
k j g a f i b l d c o e n m h
i
j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
49
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
50
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
51
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
52
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
53
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
54
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
55
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
56
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
57
k j g a f i b l d c o e n m h
i
j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
58
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
59
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
60
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
61
k j g a f i b l d c o e n m h
i j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Beispiel
62
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Aufwand
• Aufwand – Best Case:
T(n) ≈ 2×T(n/2) + O(n) ⇒ O(n×log n) (Folge zerfällt immer in zwei gleich große Teile)
– Worst Case: T(n) ≈ T(n−1) + O(n) ⇒ O(n2) (Folge ist bereits auf- oder absteigend sortiert)
– Average Case: ...
63
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Aufwand
• Aufwand – Average case
64
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Aufwand
65
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Aufwand
66
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Aufwand
67
1 2 n+1 0
1
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Quick-Sort: Aufwand
• Average Case: T(n) = O(n×log n) • Heuristiken zur Verbesserung der
Performanz – Pivot-Element: (A[l]+A[r])/2, ... – Bei kleinen Folgen auf Insertion-Sort
wechseln (oder auch nicht: Cache-Kohärenz)
– Iterative Implementierung mit Stack
68
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort
• Idee – Quick-Sort ist schnell, wenn die beiden Teilfolgen
nach Partition() ungefähr die gleiche Größe haben. – Teile die Folge ohne Vorsortieren in
zwei gleiche Teile – Sortiere die Teilfolgen – Kombiniere die Teilergebnisse
69
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (rekursiv)
• MergeSort(A[l..r]) if l < r then m ← (l+r)/2 MergeSort(A[l..m]) MergeSort(A[m+1..r]) Merge(A[l..m,m+1..r])
• Aufruf mit: MergeSort(A,1,n)
70
vgl. mit Quick-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (rekursiv)
• Merge(A[l..m,m+1..r]) new B[1..r−l+1]; i ← 1; j ← l; k ← m+1 while j ≤ m and k ≤ r do if A[j] ≤ A[k] then B[i++] ← A[j++] else B[i++] ← A[k++] while j ≤ m do B[i++] ← A[j++] while k ≤ r do B[i++] ← A[k++] for i ← l to r do A[ i ] ← B[ i−l+1 ]
71
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
72
k j g a f i b l d c o e n m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
73
k j g a f i b l d c o e n m h
k j l d c o e n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
74
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
75
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
k j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
76
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
k j
k
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
77
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
k j
k j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
78
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
j k
k j
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
79
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
j k
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
80
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
j k e n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
81
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
j k
e n
e n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
82
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
j k
e n
e n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
83
k j g a f i b l d c o e n m h
k j l d c o e n
k j e n
j k e n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
84
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n
j k e n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
85
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
86
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
87
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
c o
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
88
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
c o
o c
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
89
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
o c
o c
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
90
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
o c
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
91
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
o c l d
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
92
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
o c l d
l d
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
93
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
o c l d
l d
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
94
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n l d c o
o c l d
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
95
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n o l d c
o c l d
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
96
k j g a f i b l d c o e n m h
k j l d c o e n
e j k n o l d c
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
97
k j g a f i b l d c o e n m h
c d o n l k e j
e j k n o l d c
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Beispiel
98
k j g a f i b l d c o e n m h
c d o n l k e j
usw.
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (rekursiv)
99
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort: Aufwand
• Das Mischen zweier Folgen der Länge L1 und L2 erfordert höchstens L1+L2 Vergleiche und genau 2×(L1+L2) Kopier-operationen (i++ in jedem Schleifendurchlauf)
• Summe aller Folgenlängen auf jeder Rekursionsstufe = n
• Anzahl der Rekursionsstufen = log(n) • Best = Worst = Average Case = O(n×log n) • Aber: Doppelter Speicherbedarf !
100
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ)
• Die Zerlegung verändert die Folge nicht. • Die top-down Rekursion steuert nur die
Reihenfolge beim Mischen. • Fasse die unsortierte Liste als Folge von
sortierten einelementigen Folgen auf. • Mische die Teilfolgen bottom-up
101
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ)
• MergeSort(A[1..n]) k ← 1 while k < n do i ← 1 while i + k − 1 < n do l ← i m ← i + k − 1 r ← Min(n, i + 2*k − 1) Merge(A[ l..m,m+1..r] ) i ← i + 2*k k ← 2*k
102
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
103
k j g a f i b l d c o e n m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
104
k j g a f i b l d c o e n m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
105
k j g a f i b l d c o e n m h
j k
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
106
k j g a f i b l d c o e n m h
j k e n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
107
k j g a f i b l d c o e n m h
j k e n c o
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
108
k j g a f i b l d c o e n m h
j k e n c o d l
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
109
k j g a f i b l d c o e n m h
j k e n c o d l b i
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
110
k j g a f i b l d c o e n m h
j k e n c o d l b i a f
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
111
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
112
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
113
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
114
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
115
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
116
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
117
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
118
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i g h m
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
119
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i g h m
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
120
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i g h m
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
121
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i g h m
c d e j k l n o
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
122
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i g h m
c d e j k l n o a b f g h i m
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
123
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i g h m
c d e j k l n o a b f g h i m
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
124
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i g h m
c d e j k l n o a b f g h i m
a b c d e f g h i j k l m n o
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ): Beispiel
125
k j g a f i b l d c o e n m h
j k e n c o d l b i a f g m h
e j k n c d l o a b f i g h m
c d e j k l n o a b f g h i m
a b c d e f g h i j k l m n o
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Merge-Sort (iterativ)
126
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort
• Idee – Bei Selection-Sort entsteht der O(n2)-
Aufwand durch die lineare Suche nach dem kleinsten (oder größten) Element in der Rest-Liste.
– Mit einer Prioritätsschlange (Heap) kann man das kleinste Element schneller finden (O(log n)-Aufwand zum Wiederherstellen der Heap-Bedingung).
127
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Definition (reprise)
• (Links-)vollständiger Binärbaum in Array-Darstellung – Vaterknoten A[i] hat die Nachfolger
A[2×i] und A[2×i+1]
• Heap-Bedingung – Node ≥ max(Left-Subtree) und
Node ≥ max(Right-Subtree) – A[i] ≥ A[2×i] und A[i] ≥ A[2×i+1]
128
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Definition (reprise)
• (Links-)vollständiger Binärbaum in Array-Darstellung – Vaterknoten A[i] hat die Nachfolger
A[2×i] und A[2×i+1]
• Heap-Bedingung – Node ≥ max(Left-Subtree) und
Node ≥ max(Right-Subtree) – A[⎣i/2⎦] ≥ A[ i ]
129
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Definition (reprise)
• Ein Array A hat die Heap-Eigenschaft ab Index p, wenn A[⎣i/2⎦] ≥ A[ i ] ab Index 2×p gilt (weil dann ⎣i/2⎦ = p).
• Insbesondere: jedes beliebige Array A[1..n] hat die Heap-Eigenschaft ab Index ⎣n/2⎦+1.
130
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort
• Konvertiere ein beliebiges Array in einen Heap (A[⎣i/2⎦] ≥ A[ i ]).
• Entferne sukzessive das Top-Element und stelle die Heap-Eigenschaft wieder her (vgl. Deq()-Operation für Prioritäts- schlangen in Abschnitt 1.4).
• Heap liefert sortierte Elemente.
131
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort
• Sei A[1..n] ein Heap,Top-Element A[1] • Nach dem Entfernen des Top-
Elementes wird A[n] nach A[1] kopiert und durch „Versickern“ die Heap-Eigenschaft wieder hergestellt.
• Danach benutzt der Heap noch die Array-Elemente A[1..n−1].
• A[n] ist also frei und das entfernte Top-Element kann dort abgelegt werden.
132
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Algorithmus
• ConvertToHeap(A[1..n]) for i = ⎣n/2⎦ downto 1 do Sink(A[1..n],i)
• Wenn die Schleife bis i=p durchgelaufen ist, hat das Array A ab Index p die Heap-Eigenschaft.
133
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Algorithmus
• Sink(A[1..n],i) while i ≤ ⎣n/2⎦ do j ← 2*i if j < n and A[ j+1] > A[ j ] then j ← j+1 if A[ j ] > A[ i ] then Swap(A[ j ],A[ i ]) i ← j else i ← n
134
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Algorithmus
• HeapSort(A[1..n]) ConvertToHeap(A[1..n]) for i ← n downto 1 do Swap(A[1],A[i]) Sink(A[1..i−1],1)
135
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
136
27 19 35 44 14 41 7 11
27
19 35 44 14
41
7
11
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
137
27 19 35 44 14 41 7 11
27
19 35 44 14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
138
27 19 35 44 14 41 7 11
27
19 35 44 14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
139
27 19 35 44 14 41 7 11
27
19 35 44 14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
140
27 19 35 44 14 41 7 11
27
19
35 44 14 41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
141
27 19 35 44 14 41 7 11
27
19
35 44 14 41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
142
27 19 35 44 14 41 7 11
27
19
35
44
14 41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
143
27 19 35 44 14 41 7 11
27
19
35
44
14 41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
144
27 19 35 44 14 41 7 11
27
19
35
44
14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
145
27 19 35 44 14 41 7 11
27 19 35
44
14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
146
27 19 35 44 14 41 7 11
27 19 35
44
14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
147
27 19 35 44 14 41 7 11
27 19 35
44
14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
148
27 19 35 44 14 41 7 11
27
19 35
44
14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
149
27 19 35 44 14 41 7 11
27
19 35
44
14
41
7
11
Phase I: Aufbau des Heaps
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
150
27 19 35 44 14 41 7 11
27
19 35
44
14
41
7
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
151
27 19 35 44 14 41 7 11
27
19 35
7
14
41
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
152
27 19 35 44 14 41 7 11
27
19 35
7
14
41
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
153
27 19 35 44 14 41 7 11
27
19
35
7 14
41
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
154
27 19 35 44 14 41 7 11
27
19
35
7 14
41
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
155
27 19 35 44 14 41 7 11
27
19
35
7
14
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
156
27 19 35 44 14 41 7 11
27
19
35
7
14
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
157
27 19 35 44 14 41 7 11
27 19
35
7 14 11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
158
27 19 35 44 14 41 7 11
27 19
35
7 14 11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
159
27 19 35 44 14 41 7 11
27 19
7 14
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
160
27 19 35 44 14 41 7 11 27
19
7 14
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
161
27 19 35 44 14 41 7 11 27
19
7 14
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
162
27 19 35 44 14 41 7 11
19
7
14
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
163
27 19 35 44 14 41 7 11 19
7
14
11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
164
27 19 35 44 14 41 7 11 19
7
14 11
Phase II: Selection-Sort
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Beispiel
165
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Heap-Sort: Aufwand
• Aufwand – Aufwand zum Aufbau des Heaps – Aufwand Selection-Sort
166
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: ConvertToHeap()
• ConvertToHeap() – Sink()-Operation = O(Höhe des Heap) – Sei n = 2k −1...
167
n = 31, k = 5
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: ConvertToHeap()
168
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: ConvertToHeap()
169
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: ConvertToHeap()
170
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: ConvertToHeap()
171
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: Selection-Sort
• Selection-Sort – Kosten für die Wiederherstellung der
Heap-Eigenschaft = O(Höhe des restlichen Heaps)
– Sei n = 2k −1...
172
n = 31, k = 5
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: Selection-Sort
• Selection-Sort – Kosten für die Wiederherstellung der
Heap-Eigenschaft = O(Höhe des restlichen Heaps)
– Sei n = 2k −1...
173
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: Selection-Sort
• Selection-Sort – Kosten für die Wiederherstellung der
Heap-Eigenschaft = O(Höhe des restlichen Heaps)
– Sei n = 2k −1...
174
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: Selection-Sort
• Selection-Sort – Kosten für die Wiederherstellung der
Heap-Eigenschaft = O(Höhe des restlichen Heaps)
– Sei n = 2k −1...
175
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: Selection-Sort
• Selection-Sort – Kosten für die Wiederherstellung der
Heap-Eigenschaft = O(Höhe des restlichen Heaps)
– Sei n = 2k −1...
176
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwand: SelectionSort
177
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Aufwandsabschätzung
• Insgesamt ... worst / average case
T(n) = T1(n) + T2(n) = O(n) + O(n×log n ) = O(n×log n)
• Best case: O(n) ... alle Elemente gleich
• Vorsortierung wird nicht ausgenutzt
178
Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer
Vergleich
179
Average" Worst"
Quick-Sort" O(n×log n)" O(n2)"
Merge-Sort (doppelter Speicher)"
O(n×log n)" O(n×log n)"
Heap-Sort" O(n×log n)" O(n×log n)"