4.3.6 QuickSort - swl.htwsaar.de · a 3 2 1 4 5 7 9. 97 Partitionieren eines Arrays anhand eines Pivots § Eine elegante Methode, um ein gegebenes Array anhand eines Pivots zu partitionieren

94

4.3.6 QuickSort§ QuickSort ist ein Sortieralgorithmus, der auf der Idee

des Teile & Beherrsche beruht, und das gegebeneArray an Ort und Stelle (in place) sortiert

§ QuickSort teilt das gegebene Array anhand eines Werts darin, dem sogenannten Pivot, in zwei Teile auf, so dassalle Werte im linken Teil kleiner gleich undalle Werte im rechten Teil größer als der Pivot sindund ruft sich dann rekursiv auf den beiden Teilen auf

Informatik 1 / Kapitel 4: Algorithmen

95

Vertauschen von zwei Werten in einem Array§ Wir führen eine Hilfsfunktion ein, um in einem gegebenen

Array a die Werte an den Indizes i und j zu vertauschen


1 void swap(int [] a, int i, int j) {2 int t = a[i];3 a[i] = a[j];4 a[j] = t;5 }

96

Partitionieren eines Arrays anhand eines Pivots§ Gegeben ein Array a und einen Wert a[p] darin, dem

Pivot, wie können wir das Array so umstellen, dass alle Werte, die kleiner gleich als der Pivot sind links davon und alle größeren Werte rechts vom Pivot stehen?

§ Die Reihenfolge der Werte in den Teilen links undrechts vom Pivot soll hierbei keine Rolle spielen


Pivot3 9 7 2 5 4 1a

3 2 1 4 5 7 9a

97

Partitionieren eines Arrays anhand eines Pivots§ Eine elegante Methode, um ein gegebenes Array anhand

eines Pivots zu partitionieren. d.h. aufzuteilen,funktioniert wie folgt

§ stelle den Pivot ans Ende des Arrays

§ durchlaufe die Werte im Array und zähle wie viele Wertekleiner gleich dem Pivot bereits beobachtet wurden

§ wird ein Wert kleiner gleich dem Pivot beobachtet,stellt man ihn hinter die bisher beobachtetenWerte, die kleiner gleich als der Pivot sind

§ stelle den Pivot hinter die Werte,die kleiner gleich sind als er


98

Partitionieren eines Arrays anhand eines Pivots


1 int partition (int [] a, int l, int r, int p) {2 int pn = l;3 int pv = a[p];4

5 // Stelle Pivot ans Ende6 swap(a, p, r);7

8 // Stelle Werte kleiner als Pivot nach rechts9 for (int i = l; i < r; i++) {

10 if (a[i] <= pv) {11 swap(a, pn , i);12 pn ++;13 }14 }15

16 // Stelle Pivot an richtige Stelle17 swap(a, r, pn );18

19 return pn;20 }

99

Partitionieren eines Arrays anhand eines Pivots§ Beispiel: Partitionieren des folgenden Arrays

mittels des Aufrufs partition(a, 0, 6, 5)


Pivot3 9 7 2 5 4 1a

0 1 2 3 4 5 6

3 9 7 2 5 1 4a pn = 1

3 9 7 2 5 1 4a pn = 1

3 9 7 2 5 1 4a pn = 1

3 2 7 9 5 1 4a pn = 2

3 9 7 2 5 1 4a pn = 0 Pivot ans Ende

100

Partitionieren eines Arrays anhand eines Pivots§ Beispiel: Partitionieren des folgenden Arrays

mittels des Aufrufs partition(a, 0, 6, 5)

§ Das Partitionieren eines gegebenen Arrays der Länge nerfolgt in linearer Laufzeit O(n)


Pivot

0 1 2 3 4 5 6

3 2 7 9 5 1 4a pn = 2

3 2 1 9 5 7 4a pn = 3

3 2 1 4 5 7 9a pn = 3 Pivot hinter Werte,die kleiner gleich sind

101

QuickSort§ QuickSort sortiert einen gegebenen Teilbereicha[l] ... a[r] eines gegebenen Arrays a,indem es den letzten Wert a[r] als Pivotverwendet, den Teilbereich partitioniertund sich auf beiden Teilen aufruft

§ Ist der betrachtete Teilbereich leer (d.h. l > r),so gibt es nichts zu tun


102

QuickSort§ Wir verwenden folgende Funktion zum Sortieren eines

gegebenen Teilbereichs a[l] ... a[r]

§ Das gesamte Array können wir dann wie folgt sortieren


1 int [] qsort(int [] a, int l, int r) {2 if (r > l) {3 int p = r;4 int pn = partition (a, l, r, p);5 qsort(a, l, pn - 1);6 qsort(a, pn + 1, r);7 }8 return a;9 }

1 int [] quickSort (int [] a) {2 return qsort(a, 0, a. length - 1);3 }

103

QuickSort§ Beispiel: Sortieren des folgenden Arrays


Pivot3 9 7 2 5 4 1a

Wert anrichtiger Stelle1 9 7 2 5 4 3a

1 2 3 9 5 4 7a

1 2 3 5 4 7 9a

1 2 3 4 5 7 9a

1 2 3 4 5 7 9a

104

Laufzeit von QuickSort§ Der schlechteste Fall, bei Wahl des Pivot als letzter Wert

im zu sortierenden Bereich, tritt bei QuickSort dann ein, wenn wir es auf ein bereits sortiertes Array anwenden

§ Beispiel:

§ Der rechte Teilbereich ist in diesem Fall immer leerund der linke Teilbereich wird in jedem Schrittum einen Wert verkleinert


1 2 3 4 5 7 9a

105

Laufzeit von QuickSort§ Damit wird zuerst ein Teilbereich der Größe n partitioniert

§ Dann ein Teilbereich der Größe (n - 1)

§ …

§ Letztlich ein Teilbereich der Größe 1

§ Das Partitionieren jedes Teilbereichs erfordert lineareLaufzeit, so dass insgesamt

Befehle ausgeführt werden und die Laufzeit in O(n2) liegt


c

312n2 ≠ 1

2n

4

106

Laufzeit von QuickSort§ Im schlechtesten Fall hat QuickSort damit quadratische

Laufzeit wie die einfachen Sortierverfahren

§ Ungünstig ist es für QuickSort, wenn sich die beidenTeilbereiche stark in ihrer Größe unterscheiden

§ Günstig ist es für QuickSort, wenn die beiden Teilbereichenahezu die gleiche Größe besitzen


107

Laufzeit von QuickSort§ Wüssten wir, dass die beiden Teilbereiche eines Arrays

der Größe n nach Partitionierung jeweils Größe n/2besitzen, so ließe sich die Laufzeit wiederummittels folgender Rekurrenz beschreiben

§ Wir wissen bereits (vgl. Laufzeit von MergeSort),dass die Laufzeit dann in O(n log n) wäre


T (n) = T⇣n2

⌘+ T

⇣n2

⌘+ n

108

Laufzeit von QuickSort§ Nehmen wir an, dass die Werte im gegebenen Array in

einer zufälligen Reihenfolge stehen (d.h. alle ihre Permutationen gleich wahrscheinlich sind), sokönnen wir bestimmen wie groß die beidenTeilbereiche im Mittel sind, d.h. denErwartungswert ihrer Größe bestimmen


109

Laufzeit von QuickSort§ Beispiel: Betrachte Arrays mit den Werten {1, 4, 7}


1 4 7

1 7 4

4 1 7

4 7 1

7 1 4

7 4 1

PivotLinks: 2 / Rechts: 0

Links: 1 / Rechts: 1





Mittelwert Links: 1 / Mittelwert Rechts: 1

110

Laufzeit von QuickSort§ Man kann zeigen, dass bei zufälliger Reihenfolge der

Werte im Array, die erwartete Größe der beidenTeilbereiche n/2 beträgt

§ Im mittleren Fall (average case), d.h. über alle möglichenEingaben, verhält sich QuickSort ähnlich zu MergeSortund man sagt, dass es erwartete Laufzeit in O(n log n)


111

Robuste Implementierung von QuickSort§ Um dieses günstige Verhalten sicherzustellen, wählen

viele Implementierungen den Pivot zufällig

§ QuickSort ist ein sehr robustes, in der Praxis weit verbreitetes Sortierverfahren, das z.B. in Javain den Methoden java.util.Array.sort()zum Einsatz kommt


1 int [] qsort (int [] a, int l, int r) {2 if (r > l) {3 int p = random (l, r); // Zufallszahl in {l ,... ,r}4 int pn = partition (a, l, r, p);5 qsort(a, l, pn - 1);6 qsort(a, pn + 1, r);7 }8 return a;9 }

112

4.3.7 CountingSort§ CountingSort ist ein Sortierverfahren, welches nicht auf

Vergleichen von Werten beruht, sondern zählt wieoft jeder Wert im gegebenen Array vorkommt

§ Kommen im gegebenen Array nur wenige verschiedeneWerte jedoch wiederholt vor, so kann CountingSortmit besserer Laufzeit sortieren als vergleichendeSortierverfahren


113

CountingSort§ Wir beschreiben CountingSort für den Spezialfall, dass

ein Array bestehend aus natürlichen Zahlen {0, 1, …}zu sortieren ist

§ CountingSort lässt sich mit Hilfe einer geeigneten Datenstruktur (z.B. Hashtabelle) für beliebigeDatentypen und Werte implementieren


114

CountingSort


1 int [] countingSort (int [] a) {2 // Maximum bestimmen3 int max = -1;4 for (int i = 0; i < a. length ; i++) {5 if (max < a[i]) {6 max = a[i];7 }8 }9

10 // Werte zahlen11 int [] counts = new int[max + 1];12 for (int i = 0; i < a. length ; i++) {13 counts [a[i ]]++;14 }15

16 // Sortiertes Array erzeugen17 int i = 0;18 for (int j = 0; j < counts . length ; j++) {19 for (int k = 0; k < counts [j]; k++) {20 a[i] = j;21 i++;22 }23 }24

25 return a;26 }

115

CountingSort§ Beispiel: Sortieren des folgenden Arrays


3 2 0 2 1 4 4a max = 4

1 1 2 1 2counts

0 1 2 3 4 5 6

0 1 2 2 3 4 4a

116

Laufzeit von CountingSort§ CountingSort durchläuft das gegebene Array zweimal,

um das Maximum zu bestimmen und die darinenthaltenen Werte zu zählen

§ Die Laufzeit des Initialisierens und des abschließenden Durchlaufens des Arrays von Zählern (counts)hängt vom maximalen Wert m ab

§ Insgesamt hat CountingSort damit Laufzeit in O(n + m),welche besser als die der sortierenden Verfahrenist, sofern m << n log n gilt


117

Zusammenfassung§ QuickSort als robustes Sortierverfahren, welches auf der

Idee Teile & Beherrsche beruht und im schlechtestenFall Laufzeit in O(n2), im erwarteten Falljedoch Laufzeit O(n log n) hat

§ CountingSort als nicht-vergleichendes Sortierverfahren,welches, wenn das gegebene Array nur wenigeverschiedene Werte enthält, dieses inLaufzeit O(n + m) sortieren kann


118

Literatur

[1] H.-P. Gumm und M. Sommer: Einführung in die Informatik, Oldenbourg Verlag, 2012 (Kapitel 4)

[2] T. H. Cormen, C. E. Leiserson, R. Rivest undC. Stein: Algorithmen – Eine Einführung,Oldenbourg Verlag, 2009 (Kapitel 2)


Documents

4.3.6 QuickSort - swl.htwsaar.de · a 3 2 1 4 5 7 9. 97 Partitionieren eines Arrays anhand eines Pivots § Eine elegante Methode, um ein gegebenes Array anhand eines Pivots zu partitionieren