2.3.1 Einleitung 2.3.2 Einfache Sortierverfahren 2.3.3 Höhere Sortierverfahren … · 2015. 4. 9. · Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian

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


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


Quick-Sort

3

h k a f i b c d l o n j e g m


Quick-Sort

4

h k a f i b c d l o n j e g m h


Quick-Sort

5


d g j n i o l h c b f a e k m

h


Quick-Sort

6


d g j n i o l h c b f a e k m l d

h


Quick-Sort

7



b c n l i k j h g e f a d o m

l d

h


Quick-Sort

8




l d

h

n j f b


Quick-Sort

9



a b m l k j i h g f e c d n o


l d

h

n j f b


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



•  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



•  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


Quick-Sort: Beispiel

13

k j g a f i b l d c o e n m h



14




15


i j



16


i j



17


i j



18


i j



19


i j



20


i j



21


i j



22


i j



23


i j



24


i j



25


i j



26


i j



27


i j



28


i j



29


i j



30


i j



31


i j



32


i j



33


i j



34


i

j



35


i j



36


i j



37


i j



38


i j



39


i j



40


i j



41


i j



42


i j



43


i j



44


i j



45


i j



46


i j



47


i j



48


i

j



49


i j



50


i j



51


i j



52


i j



53


i j



54


i j



55


i j



56


i j



57


i

j



58


i j



59


i j



60


i j



61


i j



62


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


Quick-Sort: Aufwand

•  Aufwand – Average case

64


Quick-Sort: Aufwand

65


Quick-Sort: Aufwand

66


Quick-Sort: Aufwand

67

1 2 n+1 0

1


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


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


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



•  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


Merge-Sort: Beispiel

72




73


k j l d c o e n



74


k j l d c o e n

k j e n



75


k j l d c o e n

k j e n

k j



76


k j l d c o e n

k j e n

k j

k



77


k j l d c o e n

k j e n

k j

k j



78


k j l d c o e n

k j e n

j k

k j



79


k j l d c o e n

k j e n

j k



80


k j l d c o e n

k j e n

j k e n



81


k j l d c o e n

k j e n

j k

e n

e n



82


k j l d c o e n

k j e n

j k

e n

e n



83


k j l d c o e n

k j e n

j k e n



84


k j l d c o e n

e j k n

j k e n



85


k j l d c o e n

e j k n



86


k j l d c o e n

e j k n l d c o



87


k j l d c o e n

e j k n l d c o

c o



88


k j l d c o e n

e j k n l d c o

c o

o c



89


k j l d c o e n

e j k n l d c o

o c

o c



90


k j l d c o e n

e j k n l d c o

o c



91


k j l d c o e n

e j k n l d c o

o c l d



92


k j l d c o e n

e j k n l d c o

o c l d

l d



93


k j l d c o e n

e j k n l d c o

o c l d

l d



94


k j l d c o e n

e j k n l d c o

o c l d



95


k j l d c o e n

e j k n o l d c

o c l d



96


k j l d c o e n

e j k n o l d c



97


c d o n l k e j

e j k n o l d c



98


c d o n l k e j

usw.



99


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


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



•  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


Merge-Sort (iterativ): Beispiel

103




104




105


j k



106


j k e n



107


j k e n c o



108


j k e n c o d l



109


j k e n c o d l b i



110


j k e n c o d l b i a f



111


j k e n c o d l b i a f g m



112


j k e n c o d l b i a f g m h



113





114





115



e j k n



116



e j k n c d l o



117



e j k n c d l o a b f i



118



e j k n c d l o a b f i g h m



119






120






121




c d e j k l n o



122




c d e j k l n o a b f g h i m



123







124





a b c d e f g h i j k l m n o



125





a b c d e f g h i j k l m n o



126


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


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



•  (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



•  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


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


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


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



•  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



•  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


Heap-Sort: Beispiel

136

27 19 35 44 14 41 7 11

27

19 35 44 14

41

7

11


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


Heap-Sort: Beispiel

138

27 19 35 44 14 41 7 11

27

19 35 44 14

41

7

11



Heap-Sort: Beispiel

139

27 19 35 44 14 41 7 11

27

19 35 44 14

41

7

11



Heap-Sort: Beispiel

140

27 19 35 44 14 41 7 11

27

19

35 44 14 41

7

11



Heap-Sort: Beispiel

141

27 19 35 44 14 41 7 11

27

19

35 44 14 41

7

11



Heap-Sort: Beispiel

142

27 19 35 44 14 41 7 11

27

19

35

44

14 41

7

11



Heap-Sort: Beispiel

143

27 19 35 44 14 41 7 11

27

19

35

44

14 41

7

11



Heap-Sort: Beispiel

144

27 19 35 44 14 41 7 11

27

19

35

44

14

41

7

11



Heap-Sort: Beispiel

145

27 19 35 44 14 41 7 11

27 19 35

44

14

41

7

11



Heap-Sort: Beispiel

146

27 19 35 44 14 41 7 11

27 19 35

44

14

41

7

11



Heap-Sort: Beispiel

147

27 19 35 44 14 41 7 11

27 19 35

44

14

41

7

11



Heap-Sort: Beispiel

148

27 19 35 44 14 41 7 11

27

19 35

44

14

41

7

11



Heap-Sort: Beispiel

149

27 19 35 44 14 41 7 11

27

19 35

44

14

41

7

11



Heap-Sort: Beispiel

150

27 19 35 44 14 41 7 11

27

19 35

44

14

41

7

11

Phase II: Selection-Sort


Heap-Sort: Beispiel

151

27 19 35 44 14 41 7 11

27

19 35

7

14

41

11



Heap-Sort: Beispiel

152

27 19 35 44 14 41 7 11

27

19 35

7

14

41

11



Heap-Sort: Beispiel

153

27 19 35 44 14 41 7 11

27

19

35

7 14

41

11



Heap-Sort: Beispiel

154

27 19 35 44 14 41 7 11

27

19

35

7 14

41

11



Heap-Sort: Beispiel

155

27 19 35 44 14 41 7 11

27

19

35

7

14

11



Heap-Sort: Beispiel

156

27 19 35 44 14 41 7 11

27

19

35

7

14

11



Heap-Sort: Beispiel

157

27 19 35 44 14 41 7 11

27 19

35

7 14 11



Heap-Sort: Beispiel

158

27 19 35 44 14 41 7 11

27 19

35

7 14 11



Heap-Sort: Beispiel

159

27 19 35 44 14 41 7 11

27 19

7 14

11



Heap-Sort: Beispiel

160

27 19 35 44 14 41 7 11 27

19

7 14

11



Heap-Sort: Beispiel

161

27 19 35 44 14 41 7 11 27

19

7 14

11



Heap-Sort: Beispiel

162

27 19 35 44 14 41 7 11

19

7

14

11



Heap-Sort: Beispiel

163

27 19 35 44 14 41 7 11 19

7

14

11



Heap-Sort: Beispiel

164

27 19 35 44 14 41 7 11 19

7

14 11



Heap-Sort: Beispiel

165


Heap-Sort: Aufwand

•  Aufwand – Aufwand zum Aufbau des Heaps – Aufwand Selection-Sort

166


Aufwand: ConvertToHeap()

•  ConvertToHeap() – Sink()-Operation = O(Höhe des Heap) – Sei n = 2k −1...

167

n = 31, k = 5



168



169



170



171


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





– Sei n = 2k −1...

173





– Sei n = 2k −1...

174





– Sei n = 2k −1...

175





– Sei n = 2k −1...

176


Aufwand: SelectionSort

177


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


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)"

Documents

2.3.1 Einleitung 2.3.2 Einfache Sortierverfahren 2.3.3 Höhere Sortierverfahren … · 2015. 4. 9. · Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian