# 6 Sortieren für Profis

[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).

## Einleitung
Können wir die gestern gesehenen Verfahren noch ein wenig optimieren?

Das Heapsort, das wir gestern gesehen haben, hat bereits $\O(n\log n)$ Vergleiche und Bewegungen. In der Praxis hat das Heapsort einen entscheidenden Nachteil, der in unserem Analysemodell nicht gemessen wird. Wir haben ja angenommen, dass wir Zugriff auf beliebige Speicheradressen in konstanter Zeit haben. Das Heapsort nutzt das voll aus und springt beim Versickern wild im Speicher umher. Auf modernen Rechnerarchitekturen ist aber das wilde Umherspringen deutlich teurer als Zugriffe auf nahe beieinander liegende Speicherbereiche. Dieser *Caching*-Effekt macht sich bei Heapsort bemerkbar. Der zweite Wermutstropfen war, dass Heapsort immer zwei Vergleiche braucht, bis ein Element bewegt wird. Wir schauen uns Sortierverfahren an, die diese beiden Nachteile eliminieren.

## Sortieren durch Verschmelzen (Mergesort)
### Idee
Versuchen wir es mit unserer anderen Entwurfstechnik: *Divide and Conquer*.
Nehmen wir an, wir haben das Array in zwei Teile geteilt und beide Hälften schon separat sortiert. Können wir diese beiden Teile, dann schnell kombinieren?
Beginnen wir mit dem Minimum. Wenn man das Minimum finden will, dann sind normalerweise $n$ Operationen nötig. Doch das Minimum des gesamten Arrays kann nur an zwei Stellen stehen: am Anfang des linken oder am Anfang des rechten Teiles. Wir können es also mit einem Vergleich ins Ergebnis übernehmen. Das global zweitkleinste Element steht nun an einem der beiden Anfänge der Reststücke. So können wir jeweils mit nur zwei Vergleichen ein neues Element in die Gesamtreihenfolge einfügen.

### Pseudocode

mergesort(l, m, r)
	solange m-l und r-m gross genug
		mergesort(l, (m+l)/2, m-1)
		mergesort(m, (m+r)/2, r)
		merge(l,m,r)
	sonst
		direkt sortieren

Wie mache ich das merge?


merge(l,m,r)
	i = l
	j = m
	k = l
	wiederhole bis i=m-1 oder j=r
		if A[i] < A[j]
			B[k] = A[i]
			i += 1
		else
			B[k] = A[j]
			j += 1
		k += 1
	übernehme den Rest (ohne Schlüsselvergleiche)
	Kopiere B zurück nach A

In jedem Schritt schauen wir die zwei Elemente an, übernehmen das kleiner und schieben den Zeiger in a eins weiter. Sobald einer der Teile vollständig eingefügt wurde, brechen wir ab und übernehmen den Rest des anderen Teils.

### Analyse
**Schlüsselvergleiche:** $T(n) = 2 \cdot T(\frac{n}{2}) + (n-1)$, was $\O(n \log n)$ ergibt.
**Bewegungen:** ebenfalls $\Theta(n \log n)$.
**Extraplatz:** $\Theta(n)$.

Ziel erreicht! Wir haben es geschafft beides auf $n\log n$ zu reduzieren und Mergesort arbeitet auf lokalen Bereichen und ist also cache-effizienter als Heapsort.
Aber es gibt wieder ein Wermutstropfen: Wir brauchen viel Extraplatz, nämlich linear viel für den Zusatzarray $B$, also $\Theta(n)$. Also: *"Alles bestens mit Mergesort, ausser der lineare Extraplatz."*

### Reines 2-Wege-Mergesort
Die rekursiven Aufrufe im Mergesort machen gar nicht viel ausser mit den Indices herumzurechnen. Stattdessen kann man es auch *Bottom up* machen, so wie mit der Struktur des Heaps. Dazu sortieren wir zuerst die Teilstücke der Länge zwei, dann kombinieren (mergen) wir immer je zwei Stücke zu Teilstücken der Länge vier. So gehen wir durch alle Zweierpotenzen, bis wir die Länge des Arrays erreichen.

### Natürliches Mergesort
Wenn die Eingabe bereits viele vorsortierte Stücke hat, dann können wir es noch etwas schneller machen, indem wir die vorsortierten Stücke (englisch *Runs*) jeweils so lassen und damit paarweise, bottom up zusammenfügen. Bei $k$ Stücken haben wir so nur $n\log(k)$ Laufzeit und brauchen so bei schon sortierter Eingabe nur lineare Zeit.

## Quicksort
### Idee
Wir wollen die rekursive, divide-and-conquer Idee nochmal versuchen. Würden wir beispielsweise mit dem Median-Verfahren von Blum den Median bestimmen und dann den Array so umgruppieren, dass der Median in der Mitte liegt, alles kleineren links und alle grösseren rechts.


So könnten wir den Array in zwei Teile teilen und beide separat sortieren. Anschliessend sind wir gleich fertig. Gegenüber Mergesort ist also kein Merge-Schritt mehr nötig.

### Pseudocode

quicksort(l,r)
	if l<r then
		wähle pivot := A[r]
		aufteilen(l,r,k)
		quicksort(l,k-1)
		quicksort(k+1,r)

Wir wollen darauf achten, dass wir das Array *in situ* aufteilen. Wie machen wir das?
Wir führen zwei Zeiger ein, die durch den Array wandern. Einer von links her, einer von rechts her. Wir schauen also von beiden Enden des Arrays bis wir links ein Element finden, das noch nach dem Sortieren rechts stehen sollte und umgekehrt. Dann tauschen wir sie einfach miteinander.

aufteilen(l,r,k)
	nimm A[r] als pivot
	i := l
	j := r-1
	while i < j
		while (A[i] < A[r]) do i := i+1
		while (A[j] > A[r]) do j := j-1
		if i<j then 
			tausche A[i], A[j] und weiterloopen 
		else 
			tausche A[i] und A[r] und stop loop
	k := i


#### Implementierungsdetails
In der Aufteilen-Funktion müssen wir etwas vorsichtig, dass wir nie über den Rand hinausfallen können. Wir könnten einfach im While-Loop jeweils prüfen, ob beide Pointer noch im Bereich des Arrays sind - aber das ist recht langsam, da so in jedem Durchlauf statt nur einem nun zwei Vergleiche gemacht würden (Vergleich der Schlüssel und Vergleich der Pointer-Positionen). Stattdessen ist es ein guter Trick, einfach zu Beginn ein Element mit $-\infty$ einzufügen. Am rechten Rand ist dies nicht nötig, da wir dort jeweils das Pivot-Element als Rand-Element haben.

### Analyse
#### Anzahl Vergleiche
Kümmern wir uns zuerst um die Anzahl der Schlüsselvergleiche. Fürs Aufteilen von $n$ Elementen brauchen wir $n-1$ Vergleiche. Daher gilt $T(n) = n - 1 + T(k-1) + T(n-k)$. Die Laufzeit hängt also davon ab, wo das Pivotelement zu liegen kommt.

**Bester Fall:** Pivot liegt immer in der Mitte: $T(n) = (n-1) + 2 T\left( \frac{n}{2} \right) = \O(n \log n)$

**Schlimmster Fall:** Pivot liegt immer ganz am Rand: $T(n) = n-1 + T(n-1) = \O(n^2)$

**Durchschnittlicher Fall:** Wie gut ist das Verfahren "im Durchschnitt"? Wie oft kommt dieser schlimmster Fall vor?
Nehmen wir an, alle Permutationen der $n$ Elemente sind gleich wahrscheinlich als Eingabe. Dann ist das letzte Element (der Pivot) ein gleichverteilt zufälliges Element aus dem Array. Deshalb erhoffen wir uns, dass wir oft einen guten Pivot finden und daher näher bei $n\log n$ sind als bei $n^2$ sein werden. Die Analyse dazu machen wir später.

Die Wahl des Pivots als letztes Element war vorher ja recht ad hoc (ohne guten Grund). Insbesondere führt es dazu, dass schon sortierte Folgen eine Laufzeit von $\O(n^2)$ haben, weil wir immer nur ein einzelnes Element abtrennen. Wenn wir stattdessen jeweils das Element in der Mitte des Arrays als Pivot wählen, dann können wir dieses Problem beheben.

In der Praxis bewährt sich jedoch ein anderer Trick: Statt ein fixes Element als Pivot zu wählen, ist es besser drei Elemente (entweder zufällige oder deterministische) zu wählen und dann den Median dieser drei Element als Pivot zu verwenden (genannt *"Median of Three"*). Für eine deterministische Variante können wir natürlich wieder pathologische Worst-Case-Beispiele konstruieren, wo jeder Pivot nur ein Element abtrennt - aber es ist deutlich aufwändiger - und randomisiert funktioniert es richtig gut.

Intuitiv, kann es bei einem randomisierten Pivot schon auch passieren, dass wir nur ein Element abtrennen. Aber eben nur selten. Dass wir genau die Mitte treffen ist etwa gleich wahrscheinlich. Wenn wir abwechslungsreiche die Mitte und den Rand erwischen, sähe das etwa so aus und endet in Rekursionstiefe $2 \log n$:

Jetzt aber zur formalen Berechnung der Average Case Complexity von randomisiertem Quicksort.
$T(n) =\frac{1}{n} \sum_{k=1}^{n} (T(k-1) + T(n-k)) + n-1$
Behauptung: $T(n) \leq 4 n log n$

**Beweis durch Induktion:**
Induktionsanfang: $T(1) = 0$
Induktionsannahme: $\forall n' < n:$ $T(n') \leq 4 n' log n'$
Induktionsschritt:
$$\begin{align}
T(n) &= \frac{2}{n} \sum_{k=1}^{n-1} T(k) + n-1\\
&\stackrel{\text{I.A.}}{\leq} \frac{2}{n} \sum_{k=1}^{n-1} 4k logk + n-1\\
&= \frac{8}{n} \left( \sum_{k=1}^{n/2} k \log k + \sum_{k=n/2+1}^{n-1} k \log k \right) + n-1\\
&\leq \frac{8}{n} \left( \sum_{k=1}^{n/2} k (\log n-1) + \sum_{k=n/2+1}^{n-1} k \log n \right) + n-1\\
&\leq \frac{8}{n} \left(\frac{1}{2}\left(1+\frac{n}{2}\right) \frac{n}{2} (\log n-1) + \log n \left(\frac{n}{2}+1+n-1\right)\left(\frac{n}{2}-1\right) \right) + n-1\\
&\leq \frac{8}{n} \left( \frac{n}{4} \left(\log n \right)- \frac{n}{4} + \frac{n^2}{8} \log n - \frac{n^2}{8} + \log n \frac{3}{8} n^2 - \log n \frac{3}{4} n \right) + n-1\\
&\leq 2 \log n - 2 + n \log n - n + 3 n \log n - 6 \log n + n - 1\\
&\leq 4 n\log n - 4 \log n -3\\
&\leq 4 n\log n
\end{align}$$

Daraus folgt für die Anzahl Vergleich von Quicksort:
**Best Case:** $\Theta(n\log n)$
**Worst Case:** $\Theta(n^2)$
**Im Mittel:** $\Theta(n\log n)$

#### Anzahl Tauschoperationen
**Im besten Fall:** gar keine Tauschoperationen bei schon sortierten Eingaben.

**Im schlimmsten Fall:** Kein Element wird mehr als $n$ mal bewegt. Wir bekommen also sofort die Schranke $\O(n^2)$. Aber ist es wirklich so schlecht? Kann es passieren, dass *viele* Elemente *n* mal verschoben werden?
Das formale Argument, dass dies nicht passieren kann ist das folgende: Wir führen ein Konto pro Element, um die Tauschoperationen immer nur einem der beiden Zahlen, die bei einem Tausch involviert sind, anzurechnen. Wenn wir die Tauschoperation immer dem Element anrechnen, das im kleineren der beiden Teile liegt, dann kann jedes Element höchstens $\log n$ Kosten ansammeln (es kann höchstens $\log n$ mal im kleineren der beiden Teile liegen und wird pro Aufteilung höchstens einmal vertauscht). Summiert man diese Kosten auf, so kommt man also auf höchstens $n\log n$ Tauschoperationen im Worst Case!

#### Extraplatz

##### Linearer Extraplatz
Haben wir wirklich ein In-Situ Verfahren gefunden? Wie gross ist unser Extraplatz?

Im schlimmsten Fall wird die Rekursionstiefe linear, beispielsweise bei der sortierten Eingabe. Dann braucht der Rekursionsstack linearen Extraplatz für die Bereichszeiger, nicht fürs Kopien der Schlüssel selbst.

![Uploading file..._1ep83g5gv]()

Kann man bei der Rekursionstiefe noch was rausholen?

##### Logarithmischer Extraplatz

Da wir immer zwei rekursive Aufrufe machen, müssen wir uns irgendwie die beiden Teile merken und können die Rekursion also nicht einfach in eine Schleife umwandeln. Aber wir können zumindest einen der beiden Aufrufe iterativ machen. Wenn wir dafür immer den kleineren der beiden Bereiche wählen, so wird die Rekursionstiefe höchstens $\log n$ sein.

quicksort(l,r)	
	while l < r then 
		aufteilen (l,r,k)
		// Rekursiv den kleineren Teil sortieren
		if (k-1 < r-k) then
			quickssort(l,k-1)
			l = k+1
		else 
			quicksort(k+1,r)
			r = k-1
		// Nun wird der grössere Teil iterativ sortiert

Damit erreichen wir nun $\O(\log n)$ Extraplatz.

##### Konstanter Extraplatz
Für Jahrzehnte war es unklar, ob es noch besser geht, also mit konstantem Extraplatz. Das geht in der Tat mit folgender Idee.

Bevor wir in den linken Teil der Rekursion absteigen, müssen wir uns den Pivot $p$ irgendwie merken. Doch wie soll das gehen ohne Extraplatz? Wir merken uns die Grenze $p$, die den als zweites zu sortierenden Teilbereich markiert, mit Hilfe von $q$, dem Pivot des Bereichs links von $p$. Statt die Grenze $p$ explizit als Funktionsargument auf den Stack zu kopieren, "verstecken" wir sie an der Position an der sonst das Pivot $q$ steht. Ist der linke Teil sortiert, so können wir die Länge des rechten Teils rekonstruieren, indem wir einfach nach rechts gehen, bis wir ein Element grösser $p$ sehen. Wir vertauschen $q$ und $p$ und fahren mit dem Teil zwischen $q$ und $p$ fort. Danach wissen wir, dass der ganze Array links von $p$ sortiert ist und wir können mit dem Teil rechts von $p$ fortfahren.


Ganz so einfach ist es in der konkreten Implementierung aber dann doch nicht, denn wir müssen diesen "Versteck-Schritt" ja rekursiv mehrfach durchführen. Dabei müssen wir sicherstellen, dass wir die Kette der versteckten Pivots der Reihe nach zurücktauschen können. Wenn wir das gleiche $p$ einfach immer weiter hinunterschieben, geht das nicht. Aber man kann das zum Beispiel erreichen, wenn man nicht den Pivot versteckt, sondern das Element rechts vom Pivot. Überlegen Sie sich die Details!

Mit dieser Idee können wir Quicksort also gar mit $\O(1)$ Extraplatz implementieren.