Median und i-kleinste Elemente

Raphael Pavlidis Nam Pham HoangHTW Aalen

Manuel Zweng

Wintersemester 14/15

1

Inhaltsverzeichnis

1 Einleitung 4

2 Algorithmus Minimum 52.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Herkommlicher und zugleich Effizienter Algorithmus . . . . . . . 5

2.2.1 Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 52.2.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . 52.2.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2.4 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Algorithmus Minimum und Maximum simultan 83.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.2 Herkommlicher Algorithmus . . . . . . . . . . . . . . . . . . . . . 8

3.2.1 Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 83.2.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . 83.2.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.2.4 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.3 Effizienter Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 83.3.1 Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 83.3.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . 93.3.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.3.4 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Algorithmus 2.kleinste Element 134.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2 Herkommlicher Algorithmus . . . . . . . . . . . . . . . . . . . . . 13

4.2.1 Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 134.2.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . 134.2.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2.4 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.3 Effizienter Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 184.3.1 Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 184.3.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . 194.3.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.3.4 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5 Algorithmus i kleinste Element 255.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2 Herkommlicher Algorithmus . . . . . . . . . . . . . . . . . . . . . 25

5.2.1 Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 255.2.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . 255.2.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2.4 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.3 Effizienter Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 285.3.1 Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 28

2

5.3.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . 295.3.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.3.4 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.3.5 Beweis der Laufzeit fur Average Case . . . . . . . . . . . 32

5.4 Erweiterung des effizienten Algorithmus . . . . . . . . . . . . . . 355.4.1 Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 355.4.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . 365.4.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.4.4 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.4.5 Beweis der Laufzeit . . . . . . . . . . . . . . . . . . . . . 41

5.5 Quellenangabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3

1 Einleitung

In dieser Wissenschaftlichen Ausarbeitung werden Algorithmen veranschaulichtzur effizienten Suche des Medians und einem i kleinstem Element. Bei dieserAusarbeitung wird das Buch

”Introduction to Algorithms“ von Thomas H.

Cormen und Charles E. Leiserson als Basis verwendet. Gegeben ist immerein Array der Große n von Zahlen, zur Vereinfachung treten die enthaltenenZahlen nicht doppelt auf. Die Definition des i kleinsten Elements ist, dass esin dem Array i-1 kleinere Elemente gibt. Z.B. ware das 1.kleinste Element dasMinimum, beim 2.kleinsten Element gibt es dem entsprechend ein kleineresElement namlich das Minimum. (i-1 = 2-1 = 1)Beim Median handelt es sich um das Element, welches sich bei einem sortiertenArray in der Mitte befindet. Bei einem Array mit gerader Anzahl von Felderngibt es folglich zwei Elemente, welche sich in der Mitte befinden. In diesem Fallnehmen wir zur Vereinfachung das kleinere der beiden Elemente als Median.Bei einem Array mit ungerader Anzahl von Feldern ist der Median eindeutig.Dem entspricht d(n/2)e .kleinsten Element.

Dabei sind alle Kapitel gleich aufgebaut:

1. Definition der Problemstellung

2. Herkommlicher Algorithmus, welcher meist einfach zu implementieren ist.

3. Effizienterer Algorithmus, welcher eine kurzere Laufzeit hat.

Jeder Algorithmus wird wie folgt erlautert:

1. Eine kurze Beschreibung des Algorithmus

2. Ein Pseudo-Code zur Implementierung

3. Eine graphische Veranschaulichung

4. Angabe der Laufzeit

4

2 Algorithmus Minimum

2.1 Definition

Wir suchen das Element im Array mit dem kleinsten Wert. Bei einem aufstei-gend sortierten Array ware dies das erste Element. (A[0])

2.2 Herkommlicher und zugleich Effizienter Algorithmus

2.2.1 Beschreibung

Man nimmt das erste Element als vorlaufiges Minimum und geht dann dasgesamte Array durch. Hat man ein kleineres Element gefunden wird dieses durchdas bisher kleinste Element ersetzt.

2.2.2 Pseudo-Code

Algorithm 1 Minimum Algorithmus

Require: A[], n1: min := A[0]2: index := 03: for i := 1 to n− 1 step 1 do4: if min > A[i] then5: min := A[i]6: index := i7: end if8: end for9: return index

Require: Funktion braucht ein Array A und die Anzahl der Felder nZ.6: Schleife um das gesamte Feld durchzugehenReturn: Es der Index des Minimums zuruckgegeben

2.2.3 Beispiel

Ein Beispiel fur das Minimum.Legende:

• Rot Durchsuchtes Teil-Array

• Blau Noch zu durchsuchendes Array

• min Bisheriges Minimum

• index Index des bisherigen Minimums

5

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

min = 2

index = 0

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

min = 2

index = 0

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

min = 1

index = 2

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

min = 1

index = 2

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

min = 1

index = 2

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

min = 1

index = 2

6

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

min = 1

index = 2

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

min = 1

index = 2

Resultat: Das Minimum befindet sich im Array an der dritten Stelle(Index 2) und hat den Wert 1.

2.2.4 Laufzeit

Da man immer das gesamte Array durchsuchen muss betragt die Laufzeit desAlgorithmus im Worst, Best und Average Case O(n) mit jeweils n-1 Vergleichen.

7

3 Algorithmus Minimum und Maximum simultan

3.1 Definition

Wir suchen sowohl das kleinste Element als auch das großte Element gleichzeitigin einem Array. Bei einem aufsteigend sortierten Array ware dies das erste undletzte Element. (A[0] und A[n-1])

3.2 Herkommlicher Algorithmus

3.2.1 Beschreibung

Eine offensichtliche Vorgehensweise ware es das Array 2 mal durchzugehen.Beim ersten Durchgang wurde man nach dem kleinsten Element suchen undbeim zweiten Durchgang nach dem großten Element. Es spielt keine Rolle, nachwas man als erstes sucht. Man konnte dies auch mit einem Durchgang losen,indem man es gleichzeitig auf das Maximum und Minimum untersucht, aber ander Anzahl der Vergleiche wurde sich nichts andern.

3.2.2 Pseudo-Code

Analog Minimum.

3.2.3 Beispiel

Analog Minimum.

3.2.4 Laufzeit

Da man immer das gesamte Array durchsuchen muss betragt die Laufzeitdes Algorithmus im Worst, Best und Average Case O(n) mit jeweils 2n-2Vergleichen.

3.3 Effizienter Algorithmus

3.3.1 Beschreibung

Es gibt einen Effizienteren Algorithmus der mit weniger Vergleichen auskommt.Hierbei wird das Array in zweier Parchen unterteilt. In diesen Parchen wirdjeweils verglichen, welches das kleinere und welches das großere Element ist.Anschließend wird dann dieses kleinere Element mit dem bisherigen Minimumund das großere mit dem bisherigen Maximum verglichen.

8

3.3.2 Pseudo-Code

Algorithm 2 MinMax Algorithmus

Require: A[], n1: min := A[0]2: indexMin := 03: max := A[0]4: indexMax := 05:

6: for i := 1 to n− 2 + (n mod 2) step 2 do7: if A[i] < A[i + 1] then8: if A[i] < min then9: min := A[i]

10: indexMin := i11: end if12:

13: if max < A[i + 1] then14: max := A[i + 1]15: indexMax := i + 116: end if17: else18: if A[i + 1] < min then19: min := A[i + 1]20: indexMin := i + 121: end if22:

23: if max < A[i] then24: max := A[i]25: indexMax := i26: end if27: end if28: end for29:

30: if n mod 2 = 0 then31: if A[n− 1] < min then32: min := A[n− 1]33: indexMin := n− 134: end if35:

36: if A[n− 1] > max then37: max := A[n− 1]38: indeMax := n− 139: end if40: end if41:

42: return indexMin,indexMax

9

Require: Funktion braucht ein Array A und die Anzahl der Felder nZ.1: Initialisieren des MinimumsZ.3: Initialisieren des MaximumsZ.6: Schleife zur Paarbildung (immer in zweier Schritten, damit das erste Glieddes Paares ausgewahlt wird)Z.7: Uberprft welches der beiden Felder des Paares kleiner istZ.8: Wenn das erste Element kleiner ist: Uberpruft ob das neue Minimumkleiner ist als das alteZ.13: Uberpruft ob das neue Maximum groer ist als das alteZ.18: Wenn das zweite Element grer ist: berprft ob das neue Minimum kleinerist als das alteZ.23: Uberpruft ob das neue Maximum groer ist als das alteZ.30: Falls das Array eine ungerade Anzahl an Felder hat, besteht das letztePaar aus nur einem ElementZ.31: Dieses wird dann mit dem alten Minimum verglichenZ.36: Und hier wird es mit dem alten Maximum verglichenReturn: Es der Index des Minimums und Maximum zuruckgegeben

3.3.3 Beispiel

• Rot Durchsuchtes Teil-Array

• Blau Noch zu durchsuchendes Array

• min Bisheriges Minimum

• indexMin Index des bisherigen Minimum

• max Bisheriges Maximum

• indexMax Index des bisherigen Maximum

Minimum und Maximum werden simultan gesucht.Pro Schritt werden zwei Elemente untersucht.

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexMin=0

min=2

indexMax=0

max=2

Vergleiche:0

10

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexMin=2

min=1

indexMax=1

max=9

Vergleiche:3

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexMin=2

min=1

indexMax=4

max=10

Vergleiche:6

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexMin=2

min=1

indexMax=5

max=12

Vergleiche:9

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexMin=2

min=1

indexMax=5

max=12

Vergleiche:11

Resultat: Das Minimum befindet sich im Array an der dritten Stelle(Index 2) und hat den Wert 1.Das Maximum befindet sich im Array an der sechsten Stelle (Index 5) und hatden Wert 12.Es wurde zur erfolgreichen Suche 11 statt 14 Vergleiche benotigt.

11

3.3.4 Laufzeit

Zwar betragt die Laufzeit fur diesen Algirthmus analog wie beim Herkomm-lichen Algorithmus im Worst, Best und Average Case wieder O(n), aber manbraucht 3n/2 Vergleiche fur gerade Anzahl von Elementen. Bei ungerader An-zahl ist es 3n/2 + 2.

12

4 Algorithmus 2.kleinste Element

4.1 Definition

Wir suchen das Element im Array mit dem 2.kleinsten Wert. In einem aufstei-gend sortiertem Array ware dies das zweite Element. (A[1])

4.2 Herkommlicher Algorithmus

4.2.1 Beschreibung

Normalerweise wurde man den MinAlgorithmus (siehe Seite ??, Kapitel ??)aufrufen um das kleinste Element zu finden um es danach aus dem Array zuentfernen. Anschließend wurde man wieder den MinAlgorithmus aufrufen umdadurch das gesuchte 2.kleinste Element zu finden.

4.2.2 Pseudo-Code

Algorithm 3 SecondSmallest Algorithmus

Require: A[], n1: indexSmallest := minimum(A,n)2: smallest := A[indexSmallest]3: A[indexSmallest] :=∞4:

5: indexSecondSmallest := minimum(A,n)6: A[indexSmallest] := smallest7:

8: return indexSecondSmallest

Require: Funktion braucht ein Array A und die Anzahl der Felder nZ.1: Aufruf des Minimum-AlgorithmusZ.3: Minimum wird geloschtZ.5: Aufruf des Minimum-Algorithmus um dieses mal das 2.kleinste Elementzu finden (da das kleinste Element geloscht wurde)Return: Es der Index des 2.kleinsten zuruckgegeben

4.2.3 Beispiel

• Rot Durchsuchtes Teil-Array

• Blau Noch zu durchsuchendes Array

• min Bisheriges Minimum

• indexMin Index des bisherigen Minimum

• secSmallest Bisheriges 2.kleinste Element

• indexSecSmallest Index des bisherigen 2.kleinsten Elements

13

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=0

smallest=2

indexSecSmallest=

secSmallest=

Vergleiche:0

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=0

smallest=2

indexSecSmallest=

secSmallest=

Vergleiche:1

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=

secSmallest=

Vergleiche:2

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=

secSmallest=

Vergleiche:3

14

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=

secSmallest=

Vergleiche:4

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=

secSmallest=

Vergleiche:5

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=

secSmallest=

Vergleiche:6

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=

secSmallest=

Vergleiche:7

Jetzt wird das Minimum geloscht indem man es durch und unendlich ersetzt.Man speichert das Element aber ab, um es am Ende wieder einzufugen, damit

man wieder das selbe Array hat.

15

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=

secSmallest=

Vergleiche:7

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:8

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:9

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:11

16

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:10

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:10

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:11

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:12

17

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:13

0

2

1

9

2

∞3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:14

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

indexSmallest=2

smallest=1

indexSecSmallest=0

secSmallest=2

Vergleiche:14

4.2.4 Laufzeit

Da man immer das gesamte Array durchsuchen muss betragt die Laufzeitdes Algorithmus im Worst, Best und Average Case O(n) mit jeweils 2n-2Vergleichen.

4.3 Effizienter Algorithmus

4.3.1 Beschreibung

Es gibt einen effizienteren Algorithmus zur Suche des 2.kleinsten Elementes.Dieser Algorithmus ist aufgebaut wie ein Turnier mit K.O.-System, wobeidas kleinere Element gewinnt. Logischerweise ist der Sieger des ”Turniers”daskleinste Element (i = 1). Demzufolge, dass das kleinere Element immer gewinnt,kann das zweitkleinste Element nur vom kleinste Element besiegt werden. Dahermuss einer der Gegner des kleinsten Elements das 2.kleinste gewesen sein.

18

4.3.2 Pseudo-Code

Algorithm 4 SecondSmallest Algorithmus

Require: A[], n1: queue := 0, 1, ..., n− 12:

3: while queue.size 6= 1 do4: i := queue.extract()5: j := queue.extract()6: if A[i] < A[j] then7: queue.add(i)8: W [i].add(j)9: else

10: queue.add(j)11: W [j].add(i)12: end if13: end while14: indexMin := queue.extract()15: indexSecondSmallest := −116: secondSmallest :=∞17: while W [indexMin].hasNext do18: nextIndex := W [indexMin].getNext19: if A[nextIndex] < secondSmallest then20: secondSmallest := A[nextIndex]21: indexSecondSmallest := nextIndex22: end if23: end while24:

25: return indexSecondSmallest

Require: Funktion braucht ein Array und die Anzahl der FelderZ.1: Eine FIFO Queue wird initialisiert mit der 0 als erstes bis n als letztesZ.3: Warteschlange fur das Turnier, solangeZ.6: Die Zahlen am Index i und j werden verglichen(spielen gegeneinander)Z.7-11: Jenachdem wer gewonnen hat darf am Tunier weiter spielen indem manes in der Queue wieder hinzugefugt wirdZ.7-11: Es wird auch in einem Array[0 .. n] von Verkettetelisten(W []) gespei-chert welche Zahlen am Index i und j gegen wenn gewonnen hatZ.14: Da am Tunier nur noch einer da ist hat die Zahl gewonnen, somit ist esdas MinimumZ.17: Da wir im Array[0 .. n] von Verkettetelisten(W []) wissen gegen wem dasMinimum aufeinander getroffen hat mussen wir nur noch von der Verkettenlistedes Gewinners(indexMin) das Minimum ermittelnReturn: Es der Index des 2.kleinsten zuruckgegeben

19

4.3.3 Beispiel

• Rot Durchsuchtes Teil-Array

• Blau Noch zu durchsuchendes Array

• Grun Gegner des Minimums

• min Bisheriges Minimum

• indexMin Index des bisherigen Minimum

• secSmallest Bisheriges 2.kleinste Element

• indexSecSmallest Index des bisherigen 2.kleinsten Elements

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Vergleiche:1

2

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Vergleiche:2

2 1

20

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Vergleiche:3

2 1 10

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Vergleiche:4

2 1 10 3

21

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Vergleiche:5

2 1 10 3

1

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Vergleiche:6

2 1 10 3

1 3

22

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Vergleiche:7

2 1 10 3

1 3

1

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Vergleiche:7

2 1 10 3

1 3

1

23

Aus den Gegnern des Minimums wird das kleinste Element gesucht.

0

7

1

2

2

3

Vergleiche:7

SecSmalltest=7

0

7

1

2

2

3

Vergleiche:8

SecSmalltest=2

0

7

1

2

2

3

Vergleiche:9

SecSmalltest=2

Resultat: Das 2.kleinste Element hat den Wert 2.Es wurde zur erfolgreichen Suche 9 statt 14 Vergleiche benotigt.

4.3.4 Laufzeit

Die Laufzeit des Algorithmus betragt im Worst, Best und Average Case O(n)mit jeweils n+dln(n)e-2 Vergleichen.

24

5 Algorithmus i kleinste Element

5.1 Definition

Wir suchen das Element im Array mit dem i.kleinsten Wert. In einem aufstei-gend sortiertem Array ware dies das Element an der Stelle A[i-1].

5.2 Herkommlicher Algorithmus

5.2.1 Beschreibung

Eine einfache Vorgehensweise ware es einen Sortier-Algorithmus zu verwendenum das Array zu sortieren, dann ware das gesucht Element an der Stelle A[i-1]. Man konnte z.B. den Mergesort oder den Quicksort nehmen. Beim demHerkommlichen Algorithmus wird das ubergebene Array verandert. Bei denvorherigen Algorithmen wurde bisher immer der Index zuruck gegeben.

5.2.2 Pseudo-Code

Algorithm 5 iSmallestMerge Algorithmus

Require: A[], n, i1: merge(A,n)2: return A[i− 1]

Require: Funktion braucht ein Array A, die Anzahl n der Felder und dasgesuchte Element iZ.1: Sortieralgorithmus wird aufgerufen um das Array zu sortierenZ.2: Das Array ist sortiert und das gesuchte Element befindet sich an deri− 1.ten StelleReturn: Es der i.kleinsten Element zuruckgegeben

5.2.3 Beispiel

Wir suchen nachdem 4.kleinstem Element. Als erstes wird sortiert, in diesemFall mit dem Quicksort. Wir nehmen zur Vereinfachung immer das rechteElement vom der Partition als Pivot-Element. Zum Schluss wird das Elementmit dem Index 3 zuruck gegeben.

• Rot Nachstes Pivot-Element

• Hellrot Zu bearbeitende Partition

• Grun Vorheriges Pivot-Element

• Orange Das gesuchte Element

25

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 7 3 8 12 9 10

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 7 3 8 12 9 10

2 1 3 7

26

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 7 3 8 12 9 10

2 1 3 7

1 2 12 9 10

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 7 3 8 12 9 10

2 1 3 7

1 2 12 9 10

9 10 12

27

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 7 3 8 12 9 10

2 1 3 7

1 2 12 9 10

9 10 12

1 2 3 7 8 9 10 12

Resultat: Das 4.kleinste Element hat den Wert 7.

5.2.4 Laufzeit

Je nachdem welchen Sortier-Algorithmus man verwendet ist dem entsprechenddie Laufzeit gleich groß. Z.B. wenn man den Mergesort verwendet betragt dieLaufzeit im Worst, Best und Average-Case O(n*log(n)). Dem entsprechendware die Laufzeit wenn man den Quicksort verwendet im Worst-Case O(n2),im Best und Average-Case O(n*log(n)).

5.3 Effizienter Algorithmus

5.3.1 Beschreibung

Eine effizientere Variante ware nicht das komplette Array zu sortieren, son-dern das gewunschte Element zu suchen. Dabei verwendet man den Partitions-Algorithmus des Quicksorts ohne zu versuchen das komplette Array zu sortie-ren. Wenn wir eine Partition gebildet haben, bearbeiten wir die Partition inwelcher sich unser gewunschtes Element befindet. Man partitioniert so langebis man das gewunschte Element gefunden hat. In diesem Fall ware das Pivot-Element, nach dem man partitioniert, das gesuchte Element. Auch in diesem

28

Algorithmus verandern wir das Array und man ubergibt, wie beim vorherigenBeispiel, das Element.

5.3.2 Pseudo-Code

Algorithm 6 randomizedSelect Algorithmus

Require: A[], l, r, i1: if l = r then2: return A[l]3: end if4:

5: pivotIndex := randomizedPartition(A, l, r)6: k := pivotIndex− l7:

8: if i = k then9: return A[pivotIndex]

10: else11: if i < k then12: return randomizedSelect(A, l, pivotIndex− 1, i)13: else14: return randomizedSelect(A, pivotIndex + 1, r, i− k)15: end if16: end if

Require: Funktion braucht ein Array A, eine Variable p fur das Pivot-Element,r fur die rechte Seite der Partition, l fur die linke Seite der Partition und eineVariable i fr das gesuchte ElementZ.5: Der randomizedSelect des Quicksorts wird aufgerufenZ.8: Es wird uberpruft ob das Element gefunden wurdeZ.11: Da das Element nicht gefunden wurde, er ob man die linke Partition oderdie rechte Partition untersuchen mussZ.12 und 14: Der Algorithmus wird rekursiv aufgerufenReturn: Es der i.kleinsten Element zuruckgegeben

29

Algorithm 7 randomizedPartition Algorithmus

Require: A[], l, r1: x := A[r]2: j := l − 13:

4: for i := l to r − 1 step 1 do5: if A[i] < x then6: j := j + 17: swap(A, i, j)8: end if9: end for

10:

11: swap(A, j + 1, r)12: return j + 1

Require: Funktion braucht ein Array A, r fur die rechte Seite der Partitionund l fur die linke Seite der PartitionZ.1-2: Der Algorithmus nimmt immer das erste von rechts der Partition fur alsPivot-ElementZ.4-9: Alles was großer ist als das Pivot-Element wird rechten TeilpartitiongesetztZ.11: Das Pivot-Element wird zwischen der linken und der rechten Teilpartiti-on gesetztReturn: Es wird der Index des Pivot-Elementes welches sich nach Partitionie-rung sich befindet zuruckgegeben

5.3.3 Beispiel

• Rot Nachstes Pivot-Element

• Hellrot Zu bearbeitende Partition

• Grun Vorheriges Pivot-Element

• Orange Das gesuchte Element

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

30

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 7 3 8 12 9 10

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 7 3 8 12 9 10

2 1 3 7

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 7 3 8 12 9 10

2 1 3 7

2 1 3 7 8 12 9 10

31

5.3.4 Laufzeit

Die Laufzeit des Algorithmus betragt im Worst Case O(n2), Best Case O(n)und Average Case O(n). (Bei n Elementen)

5.3.5 Beweis der Laufzeit fur Average Case

Definition 5.1 Sei..

• ... T (n) die Laufzeitfunktion fur denn randomizedSelect(A[], l, r, i)

• ... Tpart(n) die Laufzeitfunktion fur denn randomizedPartition(A, l, r)

• ... l der Index der linke Seite der zu bearbeitende Partition. (1 ≤ l ≤ n)

• ... r der Index der rechte Seite der bearbeitende Partition. (1 ≤ r ≤ n)

• ... piv der Index des Pivot-Elements. (1 ≤ piv ≤ n)

• ... Xk binare Zufallsvariable(Indikator) mit Xk = I{A[l...piv] hat genauk Elemente}. (l − piv + 1 = k)

Beweis: Da alle Elemente eindeutig sind bedeute dies das randomizedPar-tition(A, l, r) mit gleiche Wahrscheinlichkeit eine Zahl im Bereich (1, n)zuruckgibt. Daraus folgt das E[Xk] = 1

n . Nach randomizedPartition(A, l, r)wissen nicht welche Partion man als nachsten rekursiv bearbeiten muss oderob man schon fertig ist da man das gesuchte Elemente gefunden hat. Dieshangt davon ab in welcher Partion sich das gesuchte Element befindet. Um eineObergrenze zu ermitteln, werden wir immer annehmen das sich das gesuchteElement in der großten Partition befindet. Dadurch ergibt sich folgendenUngleichung:

T (n) ≤n∑

k=1

Xk ∗ (T (max(k − 1, n− k)) + Tpart(n))

=

n∑k=1

Xk ∗ T (max(k − 1, n− k)) + Xk ∗ Tpart(n)

= Tpart(n) +n∑

k=1

Xk ∗ T (max(k − 1, n− k))

32

Da wir aber denn Average Case berechnen ergibt sich folgende Ungleichung:

E[T (n)] ≤ E[Tpart(n) +n∑

k=1

Xk ∗ T (max(k − 1, n− k))]

= E[Tpart(n)] + E

[n∑

k=1

Xk ∗ T (max(k − 1, n− k))

]

= Tpart(n) + E

[n∑

k=1

Xk ∗ T (max(k − 1, n− k))

]

= Tpart(n) +n∑

k=1

E[Xk] ∗ E[T (max(k − 1, n− k))]

= Tpart(n) +

n∑k=1

1

n∗ E[T (max(k − 1, n− k))]

= Tpart(n) +1

n∗

n∑k=1

E[T (max(k − 1, n− k))]

Betrachten wir die funktion max(n− k, k − 1) dann stellt man folgendes fest:

max(n− k, k − 1) =

{k − 1, k > dn/2en− k, k ≤ dn/2e

Daraus folgt das:

n∑k=1

E[T (max(k − 1, n− k))] ≤ 2 ∗n−1∑

k=bn/2c

E[T (k)]

Da der Term der linken Summe von T (dn/2e) bis zu T (n−1) zweimal auftauchenfur gerade n und fur ungerade n kommt noch der Term T (bn/2c) hinzu.Nehmen wir nochmal die erste Ungleichung und ersetzen wir die Summe:

E[T (n)] ≤ Tpart(n) +1

n∗

n∑k=1

E[T (max(k − 1, n− k))]

≤ Tpart(n) +1

n∗ 2 ∗

n−1∑k=bn/2c

E[T (k)]

= Tpart(n) +2

n∗

n−1∑k=bn/2c

E[T (k)]

Losen wir die Rekursion durch Substitution. Nehmen wir an das E[T (n)] ≤ cnfur eine Konstante c und fur n > 0. Ersetzten wir Tpart(n) durch an, da die

33

Partitionierung Lineare Laufzeit hat.

E[T (n)] ≤ Tpart(n) +2

n∗

n−1∑k=bn/2c

E[T (k)]

≤ an +2

n∗

n−1∑k=bn/2c

ck

= an +2c

n∗

n−1∑k=bn/2c

k

= an +2c

n∗ (

n−1∑k=1

k −bn/2c−1∑

k=1

k)

= an +2c

n∗ (

(n− 1) ∗ n2

− (bn/2c − 1)bn/2c2

)

≤ an +2c

n∗ (

(n− 1) ∗ n2

− (n/2− 2)(n/2− 1)

2)

= an +2c

n∗ (

n2 − n

2− n2/4− 3n/2 + 2

2)

= an +2c

n∗ (

n2 − n− n2/4 + 3n/2− 2

2)

= an +2c

n∗ (

3n2/4 + n/2− 2

2)

= an +c

n∗ (

3n2

4+

n

2− 2)

= an + c ∗ (3n

4+

1

2− 2

n)

= an + (3cn

4+

c

2− c

n)

< an +3cn

4+

c

2

= cn− (cn

4− c

2− an)

Als nachstes mussen wir noch ermitteln fur welche a und c Werte diese Unglei-chung cn− ( cn4 −

c2 − an) ≤ cn gilt:

cn ≥ cn− (cn

4− c

2− an)

−cn ≤ −cn + (cn

4− c

2− an)

0 ≤ cn

4− c

2− an

c

2≤ cn

4− an

c

2≤ (

c

4− a)n

c/2

c/4− a≤ n

34

Damit haben wir gezeigt das fur c/2c/4−a ≤ n diese Ungleichung gilt E[T (n)] ≤ cn.

Fur n < c/2c/4−a nehmen wir an das der Algorithmus konstate Laufzeit hat. �

5.4 Erweiterung des effizienten Algorithmus

5.4.1 Beschreibung

Die einzige Schwache des vorherigen Algorithmus ist es, dass die Moglichkeitexistiert, dass man immer ein schlechtes Pivot-Element herauszieht. Diesversucht man jetzt entgegen zu wirken, in dem man Matrizen(dn/5e) bildetum zu verhindern, dass man ein schlechtes Pivot-Element herauszieht. Alserstes wird das Array in Gruppen der Große funf aufgeteilt. Die jeweiligenGruppen werden anschließend sortiert. Daraus folgt, dass der Median derjeweiligen Gruppe sich an der Stelle mit dem Index 2 befindet. Im folgendemwird unter den gefundenen Medians wieder rekursiv nach dem Median gesucht.Hat man diesen gefunden so wird der Partitions-Algorithmus fur den Mediander Medians aufgerufen. Das Resultat ist, dass sich im Array noch mindes-tens 3n

10 −6 kleinere und 3n10 −6 großere Element befinden als das Pivot-Element.

• Orange x (Median der Medians)

• Grun Garantiert kleinere Elemente als x

• Rot Garantiert großere Elemente als x

• Blau Elemente uber die keine Aussage gemacht werden kann

1

2

7

9

10

3

8

12

17

21

6

14

16

24

30

4

11

19

22

27

13

20

23

26

29

Gruppe1

Gruppe2

Gruppe3

Gruppe4

Gruppe5

Medians

35

3n10 − 6 kommt dadurch zu Stande, da die Anzahl der Medians dn/5e ist. Hinzu

kommt noch, dass der Median der Medians garantiert immer⌈dn/5e

2

⌉− 2 klei-

nere und großere Medians hat. Da jeder Median zwei großere und zwei kleiner

Elemente besitzt, folgt daraus, dass der Median der Medians(⌈dn/5e

2

⌉− 2)∗ 3

großere und kleinere Elemente hat. Zur Vereinfachung nehmen wir aber einen

kleinere Wert namlich(⌈dn/5e

2

⌉− 2)∗ 3 ≥ 3n

10 − 6

5.4.2 Pseudo-Code

Algorithm 8 select

Require: A[], l, r, i1: if r = l then2: return A[l]3: end if4:

5: Medians := sort(A, l, r)6: x := select(Medians, 0,Medians.size− 1, (Medians.size− 1)/2)7: pivotIndex := A.indexof(x)8:

9: pivotIndex := partition(A, l, r, pivotIndex)10: k := pivotIndex− l11:

12: if k = i then13: return A[pivotIndex]14: else15: if i < k then16: return select(A, l, pivotIndex− 1, i)17: else18: return select(A, pivotIndex + 1, r, i− k)19: end if20: end if

Require: Funktion braucht ein Array A, eine Variable p fur das Pivot-Element,r fur die rechte Seite der Partition, l fur die linke Seite der Partition und eineVariable i fr das gesuchte ElementZ.5: sort gibt eine Array mit den Medians der GruppenZ.6: Der Algorithmus wird rekursiv aufgerufen um den Median der Medians zuermittelnZ.7: Es wird im ursprunglich Array ermittel wo sich der Median der Medianssich befindetZ.9: Der partition des Quicksorts wird aufgerufen mit x als Pivot-ElementZ.12: Es wird uberpruft ob das Element gefunden wurdeZ.15: Da das Element nicht gefunden wurde, er ob man die linke Partition oderdie rechte Partition untersuchen mussZ.16 und 18: Der Algorithmus wird rekursiv aufgerufen

36

Return: Es der i.kleinsten Element zuruckgegeben

Algorithm 9 sort

Require: A[], l, r1: Medians, gruppe, i2: for i := l to r − 4 step 5 do3: gruppe.clear()4: insertionSort(gruppe,A[i])5: insertionSort(gruppe,A[i + 1])6: insertionSort(gruppe,A[i + 2])7: insertionSort(gruppe,A[i + 3])8: insertionSort(gruppe,A[i + 4])9: Medians.add(gruppe[2])

10: end for11:

12: if i ≤ r then13: gruppe.clear()14: for i to r step 1 do15: insertionSort(gruppe,A[i])16: end for17: Medians.add(gruppe[(gruppe.size− 1)/2])18: end if19:

20: return Medians

Require: Funktion braucht ein Array A, r fur die rechte Seite der Partitionund l fur die linke Seite der PartitionZ.3: Das Array wird geloscht fur die neue GruppeZ.4-8: Die Element des Array wird in Gruppen der große 5 aufgeteilt und indas Array gruppe eingefugtZ.4-8: Beim einfugen wird gleich in der richtigen Stelle eingefugt damit dasArray gruppe sortiert ist wie beim Insertion-SortZ.9: Da sich der Median an der Stelle 2 liegt wird es im Array Medians hin-zugefugtZ.12-18: Wenn das Array A nicht durch 5 teilbar bleibt immer ein Rest vonElementen ubrig welchen nicht in einer Gruppe der große 5 aufgeteilen lasst,deswegen wird der Rest noch bearbeitetResultat: Es wird ein Array von Medians der Gruppen zuruckgegeben

37

Algorithm 10 partition

Require: A[], l, r, pivotIndex1: swap(A, r, pivotIndex)2: x := A[r]3: j := l − 14:

5: for i := l to r − 1 step 1 do6: if A[i] < x then7: j := j + 18: swap(A, i, j)9: end if

10: end for11:

12: swap(A, j + 1, r)13: return j + 1

Require: Funktion braucht ein Array A, r fur die rechte Seite der Partition, lfur die linke Seite der Partition und pivotIndex fur den Index des zu verwen-deten Pivot-ElementZ.1: Das Pivot-Element wird rechts von der Partition gesetztZ.5-10: Alles was großer ist als das Pivot-Element wird rechten TeilpartitiongesetztZ.12: Das Pivot-Element wird zwischen der linken und der rechten Teilpartiti-on gesetztReturn: Es wird der Index des Pivot-Elementes welches sich nach Partitionie-rung sich befindet zuruckgegeben

5.4.3 Beispiel

• Rot Nachstes Pivot-Element

• Hellrot Zu bearbeitende Partition

• Grun Vorheriges Pivot-Element

• Orange Das gesuchte Element

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

Das Array wird in Gruppe der Große funf aufgeteilt

38

1

2

7

9

10

3

8

12

Gruppe1

Gruppe2

Medians

Danach wird von den Medians der Median ermitteltIn dem man den Algorithmus rekursiv aufruft( i = 0, da man den Median

haben will)

0 1

7 8

Wieder wird das Array in Gruppe der Große funf aufgeteilt

39

7

8

Gruppe1

Medians

7 ist der Median der Medians, deswegen wird 7 als Pivot-Element genommen

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 3 7 10 12 9 8

Da wir schon das gesuchte Element gefunden haben horen wir auf

40

0

2

1

9

2

1

3

7

4

10

5

12

6

3

7

8

2 1 3 7 10 12 9 8

2 1 3 7 10 12 9 8

5.4.4 Laufzeit

Die Laufzeit des Algorithmus betragt im Worst, Best und Average Case O(n).

5.4.5 Beweis der Laufzeit

Definition 5.2 Sei..

• ... T (n) die Laufzeitfunktion fur den select(A[], l, r, i)

• ... Tpart(n) die Laufzeitfunktion fur partition(A, l, r)

• ... Tsort(n) die Laufzeitfunktion fur die Gruppen-Bildung und die Sortie-rung der Gruppen

• ... l der Index der linke Seite der zu bearbeitende Partition. (1 ≤ l ≤ n)

• ... r der Index der rechte Seite der bearbeitende Partition. (1 ≤ r ≤ n)

• ... piv der Index des Pivot-Elements. (1 ≤ piv ≤ n)

• ... x der Median der Medians

Beweis: Als erstes werden wir uns klar machen was die schlechteste Situati-on fur unsere Algorithmus ist. Zuerst mussen wir das Array in Gruppen derGroße bilden und diese Gruppen sortieren z.B. mit dem Insertion-Sort. DasArray in Gruppen zu bilden ist trivialerweise in linearer Zeit moglich und dannanschließend die einzelnen Gruppen zu sortieren auch. Da die Gruppen einefeste Große haben ist die Sortierung einer Gruppe Konstant Tsort(n). Danach

41

wird der Algorithmus rekursiv aufgerufen um x (Median der Medians) zu er-mitteln, das bedeutet das der Algorithmus ein Array der Große dn/5e zu bear-beiten hat (T (dn/5e)). Wie im vorherigen Algorithmus wir dann der Partition-Algorithmus mit dem x als Pivot-Element aufgerufen, welches auch lineare Lauf-zeit hat(Tpart(n)). Zum Schluss wird fur einer der enstandenen Partionen, derselect noch mal rekursiv aufgerufen, falls man des Element nicht gefunden hat.Im schlechtesten Fall kann die Partition die Große 7n/10 + 6 haben, da wirja wissen das x 3n/10 − 6 kleinere und großere Elemente hat (T (7n/10 + 6)).Dadurch ergibt sich folgenden Ungleichung:

T (n) ≤ Tsort(n) + T (dn/5e) + Tpart(n) + T (7n/10 + 6)

Nehmen wir an das T (n) = O(1) fur n kleiner als 140. Wie man auf 140 kommenwerden wir in einem spatern Zeitpunkt erlautern. Dadurch ergibt sich folgendenUngleichung:

T (n) ≤

{O(1), n < 140

Tsort(n) + T (dn/5e) + Tpart(n) + T (7n/10 + 6), n ≥ 140

Losen wir die Rekursion durch Substitution. Nehmen wir an das T (n) ≤ cn fureine Konstante c und fur n > 0. Ersetzten wir Tpart(n) durch an und Tsort(n)durch bn, da beide Algorithmen Lineare Laufzeit haben.

T (n) ≤ Tsort(n) + T (dn/5e) + Tpart(n) + T (7n/10 + 6)

= bn + T (dn/5e) + an + T (7n/10 + 6)

≤ bn + cdn/5e+ an + c(7n/10 + 6)

= n(a + b) + cdn/5e+ 7nc/10 + 6c

Ersetzen wir a + b durch d da a und b Konstanten sind.

T (n) ≤ dn + cdn/5e+ 7nc/10 + 6c

≤ dn + cn/5 + c + 7cn/10 + 6c

= dn + 9cn/10 + 7c

= cn− cn/10 + 7c + dn

= cn + (−cn/10 + 7c + dn)

42

Als nachstes mussen wir noch ermitteln fur welche c und d Werte diese Unglei-chung cn + (−cn/10 + 7c + dn) ≤ cn gilt:

cn + (−cn

10+ 7c + dn) ≤ cn

−cn

10+ 7c + dn ≤ 0

7c + dn ≤ cn

10

dn ≤ cn

10− 7c

dn ≤ cn− 70c

1010dn ≤ cn− 70c

10dn ≤ c(n− 70)

10dn

n− 70≤ c

10d ∗ n

n− 70≤ c

Da die Ungleichung fur n ≥ 140 gilt folgt daraus das nn−70 ≤ 2. Dadurch kann

man denn hinteren Teil der Ungleichung durch 2 ersetzen und bekommt folglich:

10d ∗ n

n− 70≤ c

10d ∗ 2 ≤ c

20d ≤ c

Dadurch haben wir bewiesen das T (n) ≤ cn fur n ≥ 140 und fur die Konstanten20d ≤ c. Wir hatten auch fur n ≥ 71 setzen konnen wir mussen nur sicherstellendas ( n

n−70) eine Obergrenze fur limn→∞ existiert. �

43

5.5 Quellenangabe

Thomas H. Cormen, Clifford Stein, Charles E. Leiserson, Robert L. Rivest:

”Introduction to Algorithms“

MIT Press 2007

44