# 3 Suchen und das Auswahlproblem

[TOC]

[comment]: # (Zuerst ein paar LaTeX-Makros:)

$\newcommand{\N}{\mathbb{N}}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\O}{\mathcal{O}}$

*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).

## Einführung

Wir wollen heute die Techniken zum Entwurf und zur Analyse von Algorithmen, die wir letzte Woche gesehen haben, auf ein erstes Themengebiet anwenden: das Suchen in Datenmengen. Wir nehmen an, dass wir $n$ Datensätze vor uns haben, die je durch einen *Schlüssel* identifiziert werden. Ein Array $A$ mit $n$ Elementen $A[1], \dots, A[n]$ bezeichnet die Schlüsselmenge dieser Datensätze und wir bekommen nun einen weiteren Schlüssel $k$, den wir in der Menge suchen. Wir wollen also wissen ob es einen Index $i \in \{1, \dots, n\}$ gibt, sodass $A[i] = k$ gilt.

Der Einfachheit halber nehmen wir meist an, dass diese Schlüssel positive ganze Zahlen sind. Es können aber auch genausogut Zeichenketten wie in einem Wörterbuch sein. Ein Beispiel:

Wir haben letzte Woche auch gelernt, dass niemand von Ihnen die Rektorin kennt. Darum dachte ich mir, schlage ich mal im ETH-Who-is-who nach, was ich über Sarah Springman herausfinde. Das ist ein dickes Buch mit 1521 Seiten und den Angaben zu rund 45'000 ETH-Absolventen.

Wenn wir nun die Rektorin darin von vorne nach hinten suchen kann das lange dauern. Man muss nicht Informatik studieren um zu sehen, dass es nicht sinnvoll ist, bei Abel und Abgottspon zu beginnen. Was würden Sie tun?

Das Verzeichnis ist zum Glück alphabetisch sortiert und das wollen wir natürlich ausnutzen. Schlagen wir das Buch in der Mitte auf bei 'Luginbühl' auf, so wissen wir sofort, dass sich die Rektorin nicht in der ersten Hälfte versteckt und können die ersten 760 Seiten von nun an getrost ignorieren. In der Mitte der zweiten Hälfte, auf Seite 1140, sind wir mit 'Sidler' schon ziemlich nahe und können erneut 380 Seiten (die erste Hälfte des Restes) wegwerfen. Nun schauen wir auf Seite $1140 + \frac{380}{2} = 1320$ und sehen, dass wir mit 'Weibel' übers Ziel hinausgeschossen sind. So ignorieren wir fortan die hintere Hälfte und fahren weiter auf Seite $1320 - \frac{190}{2} = 1225$.

TODO Skizze der binären Suche im Buch

Nach rund sieben weiteren Schritten landen wir so auf Seite 1166 zwischen 'Springer' und 'Spross' und stellen fest, dass Prof. Springman nicht an der ETH studierte^[Prof. Springman studierte und promovierte in Geotechnik an der Universität Cambridge [Homepage](http://www.geotechnics.ethz.ch/people/sarahs).]. Uns interessiert heute aber auch nicht unbedingt der Werdegang der Rektorin, sondern das Suchverfahren, das wir soeben angewendet haben.

## Binäre Suche
Wir haben ausgenutzt, dass das Alumni-Verzeichnis alphabetisch sortiert ist. Wir verlangen also von unseren Schlüsseln in $A$, dass sie entsprechend einer totalen Ordnung sortiert sind. Für ganze Zahlen kann das die aufsteigende Ordnung "<" sein und für Zeichenketten eben die lexikographische Ordnung.

Wie wir Schlüssel sortieren, werden wir nächste Woche im Detail studieren. Für heute nehmen wir einfach an, dass wir $A$ bereits sortiert vor uns haben, also
$$A[1] \leq A[2] \leq \dots \leq A[n-1] \leq A[n].$$

### Pseudocode

Das Divide-and-Conquer-Verfahren des wiederholten Halbierens und Wegwerfens, das wir vorhin angewandt haben, heisst *binäre Suche*. Divide-and-Conquer-Verfahren beschreiben wir am einfachsten rekursiv:

Binäre Suche(A, k)
: * Falls A leer ist, endet die Suche erfolglos.
* Sonst betrachte das Element A[m] an mittlerer Position m.
* Falls $k < A[m]$, rekursiv: binäre Suche in der Teilliste $A[1], \dots, A[m-1]$.
* Falls $k > A[m]$, rekursiv: binäre Suche in der Teilliste $A[m+1],\dots,A[n]$.
* Sonst ist $k = A[m]$ und wir haben das gesuchte Element gefunden.

In jedem rekursiven Aufruf passen wir also entweder das linke oder das rechte Ende der noch relevanten Teilliste an. Wir können das Verfahren daher auch leicht iterativ formulieren indem wir Schritt für Schritt die Grenzen anpassen:

binary_search(A, k)
	left := 1
	right := n
	while (left <= right) do
		middle := ⌊(left+right)/2⌋
		if (A[middle] = k) then 
			return "Gefunden an Position (middle)."
		else if (k < A[middle]) then
			right := middle-1
		else
			left := middle+1
	return "Nicht vorhanden."

### Analyse

Wie bereits bekannt, stellen wir uns zu jedem neuen Algorithmus zwei Fragen: Ist er korrekt und ist er schnell?

#### Korrektheit
Die Korrektheit der binären Suche zeigen wir am einfachsten mit Hilfe einer (aus Eiffel wohl bekannten) Schleifeninvarianten. Nach jeder Iteration gilt: "Falls das gesuchte Element in $A$ existiert, dann ist es im Bereich $A[left], \dots, A[right]$". Wir argumentieren in gewohnter Induktion:
* Induktionsanfang: Zu Beginn bezeichnet $A[left]=A[0], \dots, A[n]=A[right]$ das gesamte Array.
* Induktionsannahme: Angenommen, die Invariante gilt nach $i$ Schritten.
* Induktionsschritt: Wir zeigen, dass die Invariante nun auch nach dem $i+1$-ten Schleifendurchlauf stimmt. Falls $k < A[middle]$ gilt, setzen wir auf Zeile 8 die rechte Schranke $right$ auf $middle-1$. Aus der Induktionsannahme wissen wir, dass für das unveränderte $left$ nach wie vor $A[left] \leq k$ gilt. Da $A$ sortiert ist gilt die Schleifeninvariante also auch nach dieser Iteration. Ebenso gilt die Invariant für den anderen Fall in Zeile 9.

Die Korrektheit folgt nun aus der Invariante und daraus, dass wir die Rekursion nur dann abbrechen, falls kein Elemente mehr übrig ist oder wir $k$ gefunden haben.

#### Laufzeit
In jeder Iteration halbiert sich der verbleibende Suchbereich in etwa. Um genau zu sein sind bei einer Suche mit $n$ Elementen im nächsten Aufruf noch $\lf \frac{n}{2} \rf$ oder $\lc \frac{n}{2} \rc -1$ Elemente übrig. Wir können also schreiben:
$$T(n) = \begin{cases}
d & \text{falls } n = 1\\
T\left(\frac{n}{2}\right) + c & \text{sonst}
\end{cases}$$
Wir teleskopieren
$\begin{align}
T(n) &= T\left(\frac{n}{2}\right) + c\\
&= T\left(\frac{n}{4}\right) + 2c\\
&= T\left(\frac{n}{2^i}\right) + i\cdot c\\
&= T\left(\frac{n}{n}\right) + \log n\cdot c,
\end{align}$
was uns zur Vermutung führt: $T(n) = d + c \cdot \log n$.

**Induktionsbeweis**
* Induktionsanfang: $T(1) = d + c \log 1 = d$ ✓
* Induktionshypthese: $T\left(\frac{n}{2}\right) = d + c \log\left(\frac{n}{2}\right)$
* Induktionsschritt von $\frac{n}{2}$ nach $n$:
$T(n) = T\left(\frac{n}{2}\right) + c \stackrel{IH}{=} \left(d+c\log\left(\frac{n}{2}\right)\right) + c = d + c (\log n - 1) + c = d + c\log n$ ✓

Somit liegt die Laufzeit der binären Suche in $\Theta(\log n)$.

#### Power of the log
Führen wir uns das (eindrückliche!) Resultat dieser Analyse nochmals vor Augen. Eine Suche im Telefonbuch von vorne nach hinten skaliert nur linear mit der Grösse des Buches. Fügen wir eine Seite hinzu, so müssen wir im schlimmsten Fall eine Seite mehr anschauen. Fügen wir 100 Seiten hinzu, sind es 100 Schritte mehr. Auch wenn wir etwas cleverer sind und jeweils 10 Seiten auf einmal weiterspringen senkt dies lediglich die Steigung unserer linearen Wachstumskurve und erzielt nichts fundamental Besseres.


Was wir intuitiv machen und soeben analysiert haben, ist ein exponentieller Speedup! Solange das Telefonbuch nicht mehr als doppelt so dick wird, genügt ein einziger zusätzlicher Suchschritt.

In der Praxis kann dies locker den Unterschied zwischen unglaublich langsam und instantan ausmachen. Binäre Suche ist nur einer von vielen Algorithmen mit dieser Eigenschaft und wir wollen zur Illustration kurz ein zweites Beispiel anschauen: Ich würde gerne zählen, wieviele Studierende momentan im Raum sind. Ich könnte nun jeden Sitzplatz durchzählen ($n$ Schritte) oder minimal schneller in Doppelsitzgruppen zählen ($\frac{n}{2}$ Schritte). Was wir alle gemeinsam machen können ist folgendes Verfahren^[Quelle: [CS 50 @ Harvard, Prof. David Malan](https://study.cs50.net/binary_search)]: (etwas Morgenturnen zur frühen Stunde)
1. Stehen Sie auf und denken Sie an die Zahl $1$.
2. Suchen Sie den direkten Blickkontakt mit jemand anderem, der noch steht, und berechnen Sie die Summe Ihrer beiden Zahlen.
3. Einer von Ihnen beiden sitzt ab, der/die andere geht zurück zu Schritt 2.

Kopfrechenkünste und einigermassen gleichmässiges Timing vorausgesetzt, können wir so die Anzahl Personen in logarithmisch vielen Schritten bestimmen. Selbst für einen doppelt so grossen Vorlesungssaal würde es also nicht doppelt so lange sondern lediglich einen Schritt länger dauern.

#### Untere Schranke
Kehren wir nun zur binären Suche zurück. Die Frage "Geht es noch schneller?", die wir uns letzte Woche antrainiert haben, bleibt noch zu beantworten. Vielleicht finden wir ja gar noch einen besseren Algorithmus in $\O(\log \log n)$ oder gar $\O(1)$.

Um zu argumentieren, dass es nicht schneller geht, können wir uns einen beliebigen, deterministischen Suchalgorithmus auch als Entscheidungsbaum vorstellen, der in jedem Knoten einen Schlüsselvergleich durchführt und dann je nach Ergebnis erfolgreich endet oder in einen von zwei Teilbäumen absteigt.


Dieser Suchbaum muss nun mindestens $n$ Knoten enthalten, damit jeder mögliche Ausgang berücksichtigt wird, denn der Schlüssel $k$ kann ja theoretisch an jeder Position im Array stehen. Die Worstcase-Laufzeit des Suchalgorithmus entspricht nun der Tiefe des Baumes, also dem längsten Pfad von der Wurzel zu einem Blatt. Ein Binärbaum der Höhe $h$ hat höchstens $2^{h+1}-1$ Knoten, daher impliziert die Bedingung $n \leq 2^{h+1}-1$ dass $h \geq \lceil \log(n+1)\rceil$ gelten muss. Somit hat jeder Algorithmus mindestens logarithmische Laufzeit und die binäre Suche ist asymptotisch optimal!

Mit einem ähnlichen Argument, können wir auch zeigen, dass wir selbst im Mittel nicht schneller sein können als logarithmisch.

### Varianten

Die binäre Suche hat eine lange Geschichte und ist bekannt dafür, zwar einfach auszusehen aber trotzdem fehleranfällig in der Implementierung zu sein.

Donald Knuth schreibt in seinem Buch^[Donald Knuth. The Art of Computer Programming, Volume 3, Section 6.2.1, Seite 419], dass die binäre Suche 1946 wohl als erster nichtnumerischer Algorithmus publiziert wurde, aber fünfzehn Jahre lang niemand korrigierte, dass das beschriebene Verfahren nur für $n$ der Form $2^i-1$ funktionierte. Jon Bentley behauptet in "Programming Pearls" gar, dass es selbst unter Berufsprogrammierern nur rund 10% der Kandidaten gelingt die binäre Suche fehlerfrei zu implementieren und alle möglichen Endlosschleifen und Randfälle zu vermeiden[^BinSearchChallenge].

[^BinSearchChallenge]: Diese Blogpostserie gibt eine ausführliche Abhandlung über die gängigsten Fehler in Implementierungen der binären Suche [[Link]](https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/).

Es gibt aber auch viele durchaus sehr berechtigte Abwandlungen der binären Suche, die oft nützlich sind und wir nun betrachten wollen.

#### Interpolationssuche
Vergessen wir die Algorithmik für den Moment und überlegen wir uns, wie wir selber in einem Telefonbuch suchen. Auf der Suche nach "Springman" schlagen wir das Telefonbuch wohl nicht genau in der Mitte sondern eher etwas im hinteren Bereich auf. Wir nehmen an, dass die Nachnamen übers Alphabet halbwegs gleichmässig verteilt sind und "S" daher etwa im letzten Drittel anzutreffen sein sollte.

Genau diese Idee macht sich auch die Interpolationssuche zu Nutze. Statt $m = \lf\frac{l+r}{2}\rf$ zu wählen, interpolieren wir zwischen den Schlüsseln am Rand linear und erhalten so
$$m = \lf l + \frac{k-A[l]}{A[r]-A[l]}(r-l) \rf.$$

Diese Schätzung ist natürlich nur dann gut, wenn die Schlüsselwerte im Suchbereich einigermassen gleich verteilt sind. Im schlimmsten Fall ist diese Schätzung miserabel und die Interpolationssuche betrachtet jeden einzelnen Schlüssel. Überlegen Sie sich doch als Übungsaufgabe eine Eingabe, bei der diese $\O(n)$ Worst-Case-Laufzeit eintritt.

Man kann jedoch auch zeigen (was wir hier jedoch nicht tun), dass die Interpolationssuche im Mittel nur rund $\log \log n$ Vergleiche braucht, *wenn* die $n$ Schlüssel unabhängig gleich verteilte Zufallszahlen sind. Auf *gutmütigen* Eingabedaten kann dies also durchaus nochmals einen asymptotischen Geschwindigkeitszuwachs bedeuten.

Denksportaufgabe: Überlegen Sie sich wie Sie die Vorzüge der binären Suche und Interpolationssuche in einen einzigen Algorithmus kombinieren können.

#### Exponentielle Suche
Die binäre Suche und die Interpolationssuche setzen voraus, dass wir die Grösse der Schlüsselmenge kennen, bzw. dass wir nur endlich viele Schlüssel vor uns haben.

Für sehr grosse $n$ gibt es einen hübschen Trick, der sich *exponentielle Suche* nennt. Dabei beginnen wir mit dem Bereich $[1,1]$ und verdoppeln die Länge dieses Intervalls, bis wir sicher sein können, dass ein potentieller Schlüssel mit Wert $k$ im Bereich enthalten ist. Ab da führen wir eine binäre Suche auf dem Bereich $[1,k]$ durch.^[Den ersten Vergleich dieser binären Suche können wir uns noch einsparen, wenn wir statt mit $[1,k]$ mit $[\frac{k}{2}+1,k]$ starten.]

exponential_search(A, k)
	r := 1
	while (r <= n and k > A[r]) do
		r := 2*r
	return binary_search(A[1,..,min(r,n)], k)

Die Schleife in Zeile 3 und 4 endet spätestens nach $\log n$ Iterationen. Asymptotisch bedeutet die exponentielle Suche also keinen Overhead gegenüber der binären Suche. Der Name *exponentielle* Suche deutet also nicht auf die Laufzeit sondern das exponentielle Wachstum von $r$ hin. Falls sich $k$ weit vorne in der Schlüsselliste befindet, z.B. an Position $10$, so sind wir bereits nach konstant vielen Schritten fertig, egal wie gross $n$ ist. Wenn wir annehmen, dass in $A$ alle Schlüssel verschieden sind, also $A[i] < A[i+1]$ für alle $i$, dann können wir die Laufzeit gar in Abhängigkeit des gesuchten Schlüssels als $\O(\log k)$ angeben.


#### Suche mit Duplikaten / Prädikaten
Manchmal wollen wir aber auch explizit erlauben, dass $A$ Duplikate enthält, also nur monoton, nicht aber streng monoton anwächst. Wir wollen dann nicht nur irgendeinen Index $i$ mit $A[i]=k$ finden, sondern zum Beispiel den kleinsten solchen Index, also das erste Vorkommen von $k$ in $A$.
Überlegen Sie sich, wie Sie den Code der binären Suche anpassen müssen, um diesen Index zu finden, ohne die Schleifeninvariante und die Laufzeitanalyse zu verletzen.

## Lineare Suche

Für den Rest der Zeit vor der Pause wollen wir uns nun noch überlegen, wie schnell wir in *unsortierten* Schlüsselmengen suchen können. Das naheliegende, simple Verfahren, das die Elemente der Reihe nach mit $k$ vergleicht, heisst *lineare Suche* oder auch *sequentielle Suche*.

linear_search(A, k)
	for i := 1 to n
		if (A[i] = k) then 
			return "Gefunden an Position (i)."
	return "Nicht vorhanden."

Die lineare Suche ist offensichtlich korrekt und braucht im schlimmsten Fall $n$ Schlüsselvergleiche.

### Untere Schranke
**Erstes Argument:** Ein einfaches Argument, dass wir in unsortierten Mengen mindestens $n$ Schlüsselvergleiche brauchen, liegt auf der Hand: Wenn wir nicht jeden Schlüssel mit $k$ vergleichen, so riskieren wir Korrektheit, denn genau das Element, das wir nicht anschauen, hätte die Nadel im Heuhaufen sein können.


Dieses Argument ist aber nicht korrekt! Ein Algorithmus darf auch die Elemente von $A$ untereinander vergleichen und wir müssen begründen, warum das keine Vergleiche einsparen kann. Theoretisch können wir zum Beispiel bis jetzt nicht ausschliessen, dass ein Algorithmus die Elemente in sagen wir $\O(\log n)$ sortiert und dann in $\O(\log n)$ weiteren Schritten mittels binärer Suche nach $k$ sucht. Dass genau dies nicht passieren kann, weil wir fürs Sortieren mindestens $\O(n\log n)$ Schlüsselvergleiche benötigen, werden wir nächste Woche sehen aber wer garantiert uns, dass es keine anderen Tricks dieser Art gibt?

> Good judgement comes from experience, and experience comes from bad judgement. - Nasreddin

**Verbessertes Argument:** Sei *a* die Zahl der Vergleiche, die $k$ nicht involvieren, und $b$ die Zahl der Vergleiche mit $k$. Die $a$ Vergleiche teilen die Elemente in Gruppen ein, sagen wir $g$ Gruppen. Dabei sei eine Gruppe definiert als eine Teilmenge der Elemente, sodass darin jedes Paar von Elementen über eine Kette von Vergleichen verglichen wurde.

Zu Beginn ist die Gruppenzahl gleich $n$. Das Zusammenlegen zweier Gruppen benötigt mindestens einen Vergleich. Bei $g$ Gruppen, wurden also mindestens $n-g$ Vergleiche benutzt, also $a \geq n-g$.

Um nun nach $k$ zu suchen, brauchen wir mindestens einen Vergleich pro Gruppe, also $b \geq g$. Somit gilt für die Anzahl Vergleiche $a+b \geq n-g + g = n$.


### Minimum und Maximum bestimmen
Passen wir die lineare Suche minimal an, können wir damit auch das minimale Element in unsortierten $A$ in $n$ Schlüsselvergleichen bestimmen.

min_search(A, k)
	min = A[1]
	for i := 1 to n
		if (min > A[i]) then 
			min = A[i]
	return min

Eine interessante Frage dazu: Wenn wir sowohl das Minimum als auch das Maximum bestimen wollen, so können wir das leicht in $2n$ Schlüsselvergleichen. Doch geht es auch besser?^[Tipp: Divide-and-Conquer mit Basisfall $T(2)=1$.]

Hier ein Tipp:


Wir vergleichen die Elemente zuerst paarweise untereinander in $\frac{n}{2}$ Vergleichen. Danach kommt von jedem Paar nur noch das kleinere Element für das Minimum in Frage und analog kann nur noch das grössere das Maximum sein. Somit gelingt es uns insgesamt in $\frac{3}{2}n$ Vergleichen[^MinMaxLowerBound].

[^MinMaxLowerBound]: Man kann auch zeigen, dass es nicht besser als in $\lc \frac{3}{2} n \rc - 2$ Vergleichen gehen kann. Dies ist die Aufgabe 16 in Abschnitt 5.3.3 in Knuths The Art of Computer Programming, Volume 3. Das wurde erstmals in [diesem Paper von Ira Pohl](http://dl.acm.org/citation.cfm?id=361423) gezeigt.


---

## Das Auswahlproblem

In der zweiten Stunde betrachten wir die Suche nach Rang statt nach Wert. Zuvor stellten wir die Frage "Kommt der Schlüssel $k$ in der Menge $A$ vor?" und nun wollen wir beantworten "Was ist der $i$-kleinste Schlüssel in $A$?"

Auswahlproblem
: Abfrage nach Rang: Gegeben $A$ (nicht sortiert) und $i$, finde das $i$-kleinste Element in $A$.

Ein Beispiel: Bei einer Eingabe von $A = [5, 2, 9, 3, 11, 18, 4]$ und $i=5$ suchen wir das fünftkleinste Element in $A$, also die $9$. Für $i = \lf \frac{n}{2} \rf$ suchen wir das mittlere Element, den sogenannten *Median*.

Nehmen Sie doch alle kurz Ihre Legi hervor. Jede/r von Ihnen hat eine eindeutige achtstellige Leginummer (z.B. 10-916-617). Wir sind nun an der Median-Leginummer interessiert, um in etwa herauszufinden wie lange der "durchschnittliche" Student dieser Vorlesung schon immatrikuliert ist. Überlegen Sie sich kurz, wie sie dazu (mit oder ohne Computer) vorgehen würden? Gehen Sie reihum, um alle Leginummern auf Papier zu sammeln? Was machen Sie danach?

In dieser Stunde werden wir nun vier Verfahren sehen (zwei einfache, zwei etwas komplexere), die uns diesen Median bestimmen können.

### Erste Ansätze
**Wiederholt das Minimum entfernen:** Ein erster Ansatz verwendet, was wir vor der Pause gemacht haben: Wir bestimmen das Minimum in $A$ und entfernen es aus $A$. Danach ist das insgesamt zweitkleinste Element das Minimum im verbleibenden Array. Für das $i$-te Element wiederholen wir dieses Vorgehen $i$ mal in Gesamtlaufzeit $\O(i \cdot n) \subseteq \O(n^2)$.

Das ist nicht sehr praktikabel. Wir fragen "Wer hat die kleinste Leginummer?" und schicken ihn/sie vor die Tür. Das wiederholen wir $\lf \frac{n}{2} \rf$ mal, was dauert.

**Sortieren**: Ein weiterer naheliegender Ansatz ist die Elemente aufsteigend zu sortieren und dann einfach das $i$-te Element in der sortierten Folge anzuschauen. Wir werden nächste Woche sehen, dass wir in $\O(n \log n)$ sortieren können - eine drastische Steigerung gegenüber dem naiven $\O(n^2)$.

Häufig sind wir mit $\O(n \log n)$ bereits zufrieden, doch wir schauen uns jetzt noch zwei Verfahren an, denen es gar in $\O(n)$ gelingt, das Auswahlproblem zu lösen.

### Idee des Pivotierens

Die Grundidee ist folgende: Wir wählen ein Element $p$ aus, das wir als "Pivot"^[Pivot: Französisch für "Angelpunkt" oder "Drehpunkt"] bezeichnen. Nun zählen wir wie viele Elemente kleiner gleich $p$ sind und wie viele grösser als $p$ sind. Danach schauen wir in welchem der beiden Teile, das $i$-te Element liegen muss und ignorieren den anderen Teil fortan.


Für diesen Aufteilungsschritt gruppieren wir die Schlüssel so um, dass der Pivot zwischen den Elementen kleiner $p$ und denen grösser $p$ zu liegen kommt, was wir leicht in $\O(n)$ Schritten tun können. Damit sind die verbleibenden Elemente wieder direkt nebeneinander im Array und wir können unser Verfahren rekursiv auf diesen Teilbereich aufrufen.


Was macht ein gutes Pivot-Element aus? Ein gutes Pivot-Element soll die Schlüsselmenge möglichst gleichmässig aufteilen, sodass wir möglichst viele Elemente fortan ignorieren können. Wenn wir wiederholt gute Pivot-Elemente finden, dann reduziert sich die Schlüsselmenge rapide und wir haben schnell nur noch wenige Schlüssel vor uns.

Im schlimmsten Fall, schliesst ein Pivot aber immer nur ein einziges Element aus, z.B. wenn wir versehentlich immer wieder das Maximum als Pivot wählen aber eigentlich das Minimum suchen. Dann bräuchten wir $n$ Pivots und hätten eine Laufzeit von $\O(n^2)$. Wir sind also auf gute Pivots angewiesen!


Ein guter Pivot hat die Eigenschaft, dass er einen linearen Anteil der Schlüssel auf beiden Seiten hat, also mindestens $\epsilon\cdot n$ Schlüssel in beiden Teilen hat, für irgendein positives, konstantes $\epsilon$. Wenn es uns gelingt so einen Pivot in linearer Zeit zu finden, dann können wir auch eine lineare Zeit für den ganzen Algorithmus zeigen:
$$\begin{align}
T(n) &\leq \text{Pivot bestimmen + Aufteilen + Rekursion}\\
&= c_1 \cdot n + c_2 \cdot n + T((1-\epsilon)\cdot n)\\
&= c' \cdot n + T((1-\epsilon)\cdot n)\\
&= c' \cdot n + c' \cdot (1-\epsilon) \cdot n + T((1-\epsilon)^2\cdot n)\\
\dots &= \sum_{i=0}^{-\log_{1-\epsilon}(n)-1}(1-\epsilon)^i \cdot c' \cdot n + T((1-\epsilon)^{-\log_{1-\epsilon}(n)}\cdot n)\\
&= \sum_{i=0}^{-\log_{1-\epsilon}(n)-1}(1-\epsilon)^i \cdot c' \cdot n + T(1)\\
%\dots &= \frac{(1-\epsilon)^{-\log_{1-\epsilon}(n)}-1}{(1-\epsilon) - 1}\cdot c' \cdot n + T(1)
&\leq \frac{c' \cdot n}{1-(1-\epsilon)} + T(1) \in \O(n),
\end{align}$$
wobei wir in der letzten Zeile den Grenzwert der geometrischen Reihe benutzten, also dass $\sum_{k=0}^{\infty}a \cdot q^k = \frac{a}{1-q}$.

Es bleibt also lediglich die Frage: Wie finden wir einen solchen guten Pivot in linearer Zeit?

### Quickselect

Für die erste Idee namens *Quickselect*, die von Tony Hoare aus dem Jahr 1961 stammt, nehmen wir uns den Zufall zu Hilfe. Wir wählen einen zufälligen Schlüssel als Pivot und zählen aus, ob er mindestens $\frac{n}{4}$ Elemente auf beiden Seiten hat. Wir wollen also einen Pivot aus den $\frac{n}{2}$ mittleren Elementen. Falls wir Glück haben und gerade so einen Pivot aus der sortierten Mitte gewählt haben, sind wir fertig, ansonsten versuchen wir unser Glück einfach nochmals erneut.


#### Analyse

Was ist die Wahrscheinlichkeit dass wir einen guten Pivot wählen? Von $n$ Schlüsseln sind $\frac{n}{2}$ "gut", also liegt die Wahrscheinlichkeit $\frac{1}{2} = 50 \%$.
Wieviele Wiederholungen brauchen wir im Mittel bis wir so einen guten Pivot finden? Sei $E$ dieser Erwartungswert. Es gilt $E = 1 + \frac{1}{2} E$, denn entweder wir sind nach einem Versuch fertig, oder wir beginnen nochmals von vorne. Daraus folgt $E=2$. Im Schnitt müssen wir es also nur mit $2$ Pivots versuchen.

Somit ist die *erwartete* Laufzeit, um einen guten Pivot zu finden $\O(n)$. Da wir in jedem Pivotierungsschritt mindestens einen Viertel der Elemente ausschliessen (in der Analyse oben also $\epsilon = \frac{1}{4}$ einsetzen können), läuft damit Quickselect in erwarteter Zeit $\O(n)$.

#### Pseudocode

quickselect(A, i)
	while (true) // Suche einen guten Pivot
		wähle einen zufälligen Pivot p
		// Bestimme den Rang von p
		r := 0
		for j = 1 to n do
			if A[j] <= p then 
				r := r+1
		// Liegt p in der Mitte?
		if n/4 <= r <= 3*n/4 then
			break
	// Sind wir fertig?
	if i = r then
		return i
	// Pivotieren mit p
	teile die Elemente um p herum auf
	if i < r then
		quickselect(A[1,..,r], i)
	else
		quickselect(A[r+1,..,n], i-r)

### Median der Mediane nach Blum

Der einzige Wermutstropfen bei Quickselect ist die Einschränkung auf den Erwartungswert. Wir können also nicht garantieren, dass Quickselect in jedem Fall nur linear viele Schritte braucht. Wenn es dumm läuft und wir nie einen guten Pivot treffen, was extrem unwahrscheinlich aber möglich ist, dann terminiert Quickselect nicht einmal.

Das Ziel des letzten Algorithmus ist deshalb deterministisch einen guten Pivot finden, ohne dass die asymptotische Laufzeit darunter leidet.

#### Idee

In den 70er Jahren hatten die Forscher Blum, Floyd, Pratt, Rivest und Tarjan die entscheidende Idee dazu, die heute als "Median der Mediane nach Blum" bekannt ist.

**Algorithmus von Blum (A, i)**
: * Falls $n < n_0$ für eine Konstante $n_0 = 100$ ist, berechne das $i$-kleinste Element direkt und brich ab.
* Bilde beliebige Fünfergruppen aus den Elementen in $A$, $\lc \frac{n}{5}\rc$ viele
* Bestimme in jeder Fünfergruppe den Median direkt/naiv
* Nimm alle Fünfergruppenmediane und wende *dieses Verfahren rekursiv*^[Wir wenden es quasi als Blackbox an, ohne genau zu verstehen wie es funktioniert.] an, um den Median der Fünfergruppenmediane zu ermitteln. Verwende den resultierenden *Median der Mediane* als Pivotelement $p$ für $A$.
* Aufteilungsschritt: Teile mit $p$ und bestimme rekursiv in einem der beiden Teile das gesuchte Element.


#### Pseudocode

blum(A, i)
	if (n < 100)
		sortiere A
		return A[i]
	bilde Fünfergruppen A[1,..,5], A[6,..,10], ..
	A' := Menge der Mediane pro Gruppe
	p := blum(A',⌊⌈n/5⌉/2⌋)
	// pivotiere mit p
	r := Rang von p in A
	teile die Elemente um p herum auf
	if i < r then
		blum(A[1,..,r], i)
	else
		blum(A[r+1,..,n], i-r)

#### Analyse
Funktioniert diese komische Doppelrekursion wirklich? Finden wir so einen guten Pivot und bleibt die Laufzeit linear?

Wie gut ist dieser Pivot? Wie viele Elemente sind sicher kleiner als $p$?
Mindestens $\underbrace{3}_{\text{je Gruppe}} \cdot \underbrace{(⌈1/2 \cdot ⌈n/5⌉⌉ - 2)}_{\text{in der Hälfte aller Gruppen ausser}\atop \text{der Gruppe des Medians und der Restgruppe}} \geq \frac{3}{10}n - 6$ Elemente.

Genau gleich viele Elemente sind sicher grösser als $p$. Also erfolgt der zweite rekursive Aufruf auf höchstens $\lc 7n/10 + 6 \rc$ Elementen.


Als Rekursionsgleichung erhalten wir somit:
$$T(n) \leq T \left(\lc \frac{n}{5} \rc\right) + T\left(\lc \frac{7n}{10} + 6 \rc \right) + d \cdot n$$

Was wir noch zeigen wollen: Diese Rekursionsgleichung hat eine lineare geschlossene Form, also $T(n) \in \O(n)$.

**Beweis durch Induktion**
* Zu zeigen: $T(n) \leq c \cdot n$ für konstantes $c$.
* Induktionsanfang: Wähle $c$ gross genug, sodass $T(n) \leq c\cdot n$ für alle $n \leq n_0$.
* Induktionsannahme: Für alle $i < n$ gilt bereits $T(i) \leq c \cdot i$.
* Induktionsschritt:
$\begin{align}
T(n) &\leq T\left(\lc \frac{n}{5} \rc \right) + T\left(\lc \frac{7n}{10} + 6 \rc\right) + d \cdot n\\
&= c \cdot \lc \frac{n}{5} \rc + c \cdot \lc \frac{7n}{10} + 6 \rc + d \cdot n\\
&\leq c \cdot \frac{n}{5} + c + c \cdot \left(\frac{7n}{10} + 6 \right) + c + d \cdot n\\
&= \frac{9}{10} \cdot c \cdot n + 8 c + d\cdot n
\end{align}$

Nun wählen wir $c \geq 80 \cdot d$ und fahren fort mit
$\begin{align}
T(n) &\leq \frac{72}{80} \cdot c \cdot n + 8 c + \underbrace{\frac{1}{80} \cdot c}_{\geq d}\cdot n = \frac{73}{80} \cdot c \cdot n + 8 c = \underbrace{\left(\frac{73}{80} \cdot n + 8 \right)}_{\leq n \text{, da } n \geq 100}\cdot c \leq c \cdot n.
\end{align}$

Wir haben also mit $n_0=100$ den Basisfall gross genug gewählt, sodass hier im rekursiven Fall die additive $8$ im linearen Term $\frac{73}{80}n$ Platz hat.

**Warum Fünfergruppen?** Mit Gruppengrösse drei oder vier kommt bei der Rekursion etwas nicht strikt kleineres heraus. Die beiden Teilprobleme zusammengenommen sind nicht mehr kleiner als $n$, was keine lineare Laufzeit mehr ergibt. Alle Gruppengrössen ab fünf funktionieren aber genauso gut. Die Konstante $n_0$ muss aber auch entsprechend grösser gewählt werden, sodass die Basisfälle mit anwachsen.