# 5 Sortieren

[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
Was bisher geschah:
* Woche I: Algorithmenentwurf
* Woche II: Binäre Suche
* Woche III: Sortieren

Wir haben letzte Woche gesehen, wie wir in einem sortierten Array schnell suchen können oder Daten mit Hashing speichern. Bei der binären Suche haben wir gesehen, dass eine doppelte Datenmenge einen weiteren Suchschritt bedeutet. Das ist zwar grandios wenig, aber wächst halt doch mit der Datenmenge an. Beim Hashing war dies nicht der Fall und wir hatten eine konstante Suchzeit, zumindest im Erwartungswert. Doch wir opfern dabei nicht nur die Worst-Case-Garantie sondern auch die Ordnung. Wollen wir von einem Schlüssel zum nächstgrösseren Schlüssel in der Datenmenge (z.B. E-Mails nach Datum sortiert anzeigen, Terminkalender in chronologischer Reihenfolge), so ist dies mit Hashing nicht schnell möglich. Wie wir Datenmengen ordnen, oder eben *sortieren*, schauen wir uns diese Woche an.

Es gibt Leute, die sagen, dass Sortieren für mehr als 90% der weltweit aufgewendeten Rechnerzeit verantwortlich ist. Das ist vielleicht ein wenig übertrieben, aber Sortieren ist ein sehr wichtiges und häufiges Problem.

Will man einen Datensatz sortieren, so kann man die einzelnen Daten vergleichen. Handelt es sich beispielsweise um eine Menge von Mails, die man chronologisch sortieren will, so vergleicht man nicht zwei vollständige Mails, sondern betrachtet nur das Datum. Der Teil des Datensatzes, den man für das Sortieren verwendet, nennt man *Schlüssel.*

Wenn man die Effizienz eines Sortieralgorithmus analysiert, betrachtet man die *Anzahl Schlüsselvergleiche*, die ein Sortieralgorithmus durchführt. Je mehr Schlüsselvergleiche durchgeführt werden, desto schlechter bzw. langsamer läuft eine Sortieralgorithmus. Zusätzlich ist für die Effizienz auch die *Anzahl der Bewegungen* (z.B. Vertauschung zweier Elemente) von Daten wichtig.

## Sortieren überprüfen
Zuerst muss das Ziel klar sein: Wie erkennen wir ob ein Array sortiert ist?
Das Array heisse $A$ und sei indexiert von $1$ bis $n$. Wir können das Prüfen mit einer simplen Schleife umsetzen.

Prüfe(A):
	for i = 1 to n-1 do
		if A[i] > A[i+1] then
			ALARM
	falls nie ALARM: OK

Diese Überprüfung braucht nur maximal $n-1$ Vergleiche und kostet also $\O(n)$ Vergleiche, $\O(n)$ Zeit und $\O(1)$ Extraplatz.

## Bubblesort
### Idee
Jetzt wollen wir aber nicht nur prüfen sondern auch selber sortieren. Dazu soll uns der Prüf-Algorithmus als Vorlage dienen. Denn sobald wir abbrechen beim Prüfen, wissen wir zwei Elemente, die wir vertauschen sollten.

for i:=1 to n-1 do
	if A[i] > A[i+1] then 
		tausche A[i] mit A[i+1]

Das alleine genügt noch nicht. Die Sequenz 453 wird zu 435 ist also noch nicht sortiert. Also ist ein einziger solcher Durchlauf noch nicht genug. Darum wiederholen wir diesen Loop mehrmals, so lange bis sich nichts mehr ändert. Wie lange geht das?
*Behauptung:* Nach höchstens $n-1$ Wiederholungen ist der Array sortiert.
*Idee:* Nach dem ersten Durchlauf steht das grösste Element an der Stelle ganz rechts und wird nachher nie mehr verschoben. Damit ist nach dem zweiten Durchlauf das zweitgrössten Element an der korrekten Stelle usw. Nach $n-1$ Durchläufen sind somit alle Schlüssel am korrekten Platz.

Da die Schlüssel hier Runde für Runde an den korrekten Ort "blubbern", nennt man dieses Verfahren *Bubblesort*.

### Analyse
Wir können frühzeitig abbrechen, wenn sich in einer Runde nichts mehr ändert.

BubbleSort(A)
	for j:=1 to n-1 do
		kleiner_alarm := Nein
		for i:=1 to n-1 do
			if A[i] > A[i+1] then 
				kleiner_alarm := Ja
				tausche A[i] mit A[i+1]
		if kleiner_alarm = Nein
			STOP

Bringt diese Abbruchbedingung immer etwas?^[Nein. Ist die Eingabe zu Beginn absteigend sortiert, so werden alle $n-1$ Durchläufe benötigt.]

Bis jetzt haben wir jeweils nur auf die Anzahl Schlüsselvergleiche und auf den Extra-Platz geschaut. Was auch relevant ist, ist die Anzahl Bewegungen von Datensätzen.

Der schlimmste Fall ist die absteigend sortierte Folge als Eingabe. Dann benötigen wir $\Theta(n^2)$ Vertauschungen und Bewegungen.

Für einen bereits sortierten Array sind wir schon nach einer einzigen Schleife fertig, wenn wir Bubble-Sort klug implementiert haben. Wir können also davon profitieren, dass $A$ bereits vorsortiert ist.

### Parallelisierung
Ein schöner Aspekt des Bubblesorts ist, dass es sich leicht und schön parallelisieren lässt. Dafür brauchen wir nur einen Prozessor, der 'Compare&Swap' unterstützt, der also zwei Elemente vergleicht und sie vertauscht, falls sie verkehrt herum sortiert sind. Wenn wir $\frac{n}{2}$ Prozessoren zur Verfügung haben, dann kann man die Arbeit schön aufteilen:

Ungerade Runden:
1. Prozessor vergleicht und tauscht $a_1$, $a_2$
2. Prozessor vergleicht und tauscht $a_3$, $a_4$
3. usw.

Gerade Runden:
1. Prozessor vergleicht und tauscht $a_2$, $a_3$
2. Prozessor vergleicht und tauscht $a_4$, $a_5$
3. usw.


So sind wir nach $n$ Runden auch fertig, aber brauchen nur $\O(1)$ (oder $\O\left(\frac{n}{p}\right)$ für $p$ Prozessoren) Schritte und damit ist die Laufzeit nur noch $\O(n)$ (resp. $O\left(\frac{n^2}{p}\right)$).
Dies nennt man *Odd-Even-Transposition Sort*.

Ausser der Parallelisierbarkeit hat Bubblesort aber keine wirklichen Vorteile. Darum suchen wir nach was besserem.

## Sortieren durch Auswahl (Selection Sort)
### Idee
Wir wollen nun unser Lieblingsverfahren zum Algorithmenentwurf bemühen, die Induktion. Wir nehmen als Invariante, dass wir nach dem $i$-ten Schritt die ersten $i$ Elemente des Arrays sortiert sind und wir diese Elemente nie mehr verschieben müssen (Präfix ist "fix fertig"). Um diese Invariante aufrecht zu erhalten, fügen wir in jedem Schritt das Minimum des noch unsortierten rechten Teils ans Ende des sortierten linken Teils, also

| sortierter Teil | i | unsortierter, aber grösserer Teil |

Als Pseudocode:

SelectionSort(A)
	for i = 1 to n-1
		j = Index des Minimums im Bereich i bis n
		tausche A[i], A[j]

### Analyse

Um das Maximum zu finden brauchen wir $i-1$ Vergleiche. Somit beläuft sich die Anzahl Vergleiche wieder auf die arithmetische Reihe $\sum_{i=1}^{n-1}(i-1) \in \Theta(n^2)$.

Laufzeit: $\Theta(n^2)$ Vergleiche, $\O(n)$ Tauschoperationen, daher Zeit $\O(n^2)$.
Extraplatz: $\O(1)$.

Gegenüber Bubblesort haben wir also in der Laufzeit nichts gewonnen, aber immerhin führen wir nur noch linear viele Vertauschungen durch. Die quadratische Anzahl Vergleiche gefällt uns noch nicht. Hilft uns hier eine andere Invariante?

## Sortieren durch Einsetzen (Insertion Sort)

Nehmen wir als Invariante, dass das Präfix der Länge $i$ sortiert ist, aber nicht dass die Elemente bereits an ihrem finalen Platz sind. Diese Invariante können wir aufrecht erhalten, indem wir das neue Element einfach an der korrekten Stelle ins bisherige Teilarray einsortieren.

[1 2 7 9 | 4 | Rest] -> [1 2 4 7 9 | Rest]

Wie finden wir den Ort, wo das neue Element eingefügt werden sollte?
Wir können die Position mit binärer Suche finden: $\O(\log n)$ Vergleiche.
Dann nehmen wir das Teilstück, das einen Platz nach rechts muss, und schieben es Element für Element um eine Position nach rechts: $\O(n)$ Tauschoperationen.

InsertionSort(A)
	for i = 2 to n do
		suche binär nach A[i] im Bereich 1,..,i-1
			-> sei dies Position k
		verschiebe A[k,..,i-1] nach A[k+1,..,i]
		setze das alte A[i] nach A[k]

Total: $\O(n \log n)$ Vergleiche und $\Theta(n^2)$ Tauschoperationen (Bewegungen) und daher $\Theta(n^2)$ Laufzeit^[Das $\Theta$ in diesen Analysen beschreibt immer den schlechtesten Fall und dessen asymptotische genaue Wachstumsordnung. Also kann der Algorithmus $\Theta(n)$ Bewegungen brauchen, auch wenn wir im besten Fall, gar nichts vertauschen.].

Können wir diese vielen Vertauschungen umgehen, indem wir, anstatt eines Arrays, eine linear verkettete Liste benutzen? Weil dann könnten wir ja durch das Umbiegen zweier Zeiger ein neues Element einfügen. Das Problem: Auf einer verlinkten Liste können wir nicht binär suchen.

Bis jetzt haben wir noch keinen Algorithmus, der schneller ist als quadratische Zeit. Aber es besteht Hoffnung: Wir haben ein Verfahren mit linear vielen Bewegungen und eines mit $\O(n \log n)$ Vergleichen. Gelingt es uns das beste aus diesen zwei Welten zu kombinieren?

Wie macht man das? Das Problem bis jetzt war, dass wir jeweils viel Aufwand (lineare Zeit) betreiben mussten, um ein neues Element zu unserer Invariante hinzuzufügen. Versuchen wir unsere Invariante etwas aufzuweichen, sodass dies schneller geht.

## Heapsort
### Idee
Wir wollen uns vom Sortieren durch Auswahl inspirieren lassen, dabei aber versuchen das Auswählen ohne die linear vielen Vergleiche hinzubekommen. Wir wollen dazu dem noch unsortierten Teil des Array ein bisschen Ordnung aufdrücken, ihn also weder komplett unsortiert zu lassen noch komplett zu sortieren.

Wir stellen uns dazu vor, dass die Zahlen in A einen Binärbaum darstellen. Dabei sollen alle bis auf das letzte Niveau des Baumes voll sein. Das letzte Niveau füllen wir von links nach rechts.

Wurzel
5 Vater A: 1 2 3 4 5 6
/ \ 5 7 1 6 4 2
7 1 Kind
/ \ /
6 4 2
Blätter

Das können wir implizit machen. Die beiden Kinder von Knoten $i$, stehen an Position $2i$ und $2i+1$. Und der Vater von Knoten i steht an $\lf i/2 \rf$.

Warum ist dies eine nützliche Idee? Weil diese Baumstruktur nur eine geringe Höhe hat. Bei den Rechnungen der Binären Suche haben wir gesehen, dass wir mit einem Baum der Höhe $\log(n)$ schon $n$ Elemente unterbringen können. Wenn wir also auf diesen Niveaus des Baumes operieren können, dann können wir uns vielleicht Laufzeiten von $\log(n)$ pro Operation erhoffen.

Im Moment haben die Elemente im Baum aber noch keinerlei Struktur. Wir wollen also etwas Struktur verlangen, aber auch nicht zu viel, sonst wird es wieder linear. Was wir verlangen wollen: Für jede Eltern-Kind Beziehung, soll das grössere Element oben stehen. Der Wert im Elternknoten soll also immer grösser sein als der Wert im Kinderknoten. Dies nennt man die *Heap-Bedingung*.

Nehmen wir mal kurz an, dass die Eingabe "per Zufall" schon die Heapbedingung erfüllt, zum Beispiel so:

Wurzel
7 A: 1 2 3 4 5 6
/ \ 7 6 4 5 1 2
6 4
/ \ /
5 1 2
Blätter

Jetzt wollen wir die sortierte Folge schrittweise aus diesem Heap extrahieren. Wir können schnell herausfinden, was das letzte Element der sortierten Folge ist, denn das grösste Element muss an der Wurzel des Heaps stehen. Tauschen wir also die $2$ mit der $7$ aus.

2 A: 1 2 3 4 5 6
/ \ 2 6 4 5 1|7
6 4
/ \ X
5 1 7

Nun zwacken wir die $7$ ab und nehmen an, dass sie nicht mehr Teil vom Heap ist. Um induktiv argumentieren zu können, wäre es gut, wenn der Rest (also die ersten $6$ Elemente) wieder einen Heap bilden würden. Da nun aber die $2$ an der Wurzel steht, ist die Heapbedingung dort verletzt. Wir können die Heap-Bedingung aber leicht wieder herstellen, indem wir die neue Wurzel "versickern" lassen. Dazu schauen wir die beiden Kinder von $2$ an und nehmen das grössere Element nach oben:

6 A: 1 2 3 4 5 6
/ \ 6 2 4 5 1|7
2 4
/ \ X
5 1 7

Jetzt stimmt die Heap-Bedingung an der Wurzel wieder, aber die $2$ sollte auch noch mit der $5$ die Plätze tauschen, also weiter versickern.

6 A: 1 2 3 4 5 6
/ \ 6 5 4 2 1|7
5 4
/ \ X
2 1 7

Jetzt haben wir wieder einen Heap und - oh Wunder - das global zweitgrösste Element steht nun an der Wurzel. Also vertauschen wir die $6$ mit der $1$, zwacken die $6$ ab und lassen die $1$ versickern.

1 A: 1 2 3 4 5 6
/ \ 1 5 4 2|6 7
5 4
/ X X
2 6 7

5 A: 1 2 3 4 5 6
/ \ 5 1 4 2|6 7
1 4
/ X X
2 6 7

5 A: 1 2 3 4 5 6
/ \ 5 2 4 1|6 7
2 4
/ X X
1 6 7

### Pseudocode und Details

Heapsort(A)
	bilde einen Heap aus der Eingabe
	for i := n to 2
		tausche A[1] mit A[i]
		versickere A[1] im Bereich A[1 .. i-1]

Was noch fehlt: Wie bilden wir einen solchen Heap?
Induktiv: Nehmen wir an wir hätten schon zwei kleine Heaps und wollen ein neues Element als Wurzel der beiden hinzufügen und danach einen grossen Heap daraus erstellen. Genau dies, leistet die Funktion ``versickere``.

x
/ \
H1 H2

Machen wir die ``versickere``-Funktion noch explizit:

versickere(i,j)
	// Versickere Schlüssel an Position i
	// in einem Heap der ersten j Elemente
	if 2i < j then // Falls i noch Kinder hat.
		max = 2*i
		if 2i + 1 <= j then // Gibt es ein rechtes Kind?
			if A[2i+1] > A[2i] then // Welches Kind ist das Grössere?
				max = 2i+1
		if A[max] > A[i] then 
			// Falls das grössere Kind grösser ist als A[i]
			tausche (max, i)
			versickere(max,j)
			// lassen wir das getauschte 
			// Element weiter versickern.
	// Sonst sind wir fertig.

Nun müssen wir uns noch um die initiale Heapherstellung kümmern. Wir machen dazu *Induktion von unten*, um auch zum Bauen des Heaps wiederholt zwei kleinere Heaps zusammenzufügen. Dabei sind alle Blätter für sich alleine genommen bereits korrekte kleine Heaps. Wenn wir danach die Positionen $i$ von $\frac{n}{2}$ bis $1$ der Reihe nach runter gehen, dann haben wir jeweils einen neuen Knoten $i$ mit zwei Teilbäumen bei $2i$ und $2i+1$ darunter, die bereits die Heapbedingung erfüllen. Ein einzelnes ``versickere(i,n)`` stellt daher die Heapbedingung für den ganzen Baum an Position $i$ her.

Wie verwenden wir also dieses ``versickere`` nun genau?

Heapsort(A)
	// Heap aufbauen
	for i := n/2 down to 1
		versickere(i,n)
	// Wiederholt das Maximum ans Ende tauschen
	// und den Heap reparieren.
	for i := n down to 2
		tausche A[1] mit A[i]
		versickere(1,i-1)

### Analyse

**Wieviele Vergleiche machen wir?**

Das ``versickere`` läuft quasi einfach einem Pfad dem Baum entlang, sieht also höchstens $log(n)$ Niveaus. Auf jedem Niveau müssen wir bis zu zwei Schlüsselvergleiche machen. Somit machen wir rund $2\log n$ Vergleiche pro ``versickere``.

Somit machen wir insgesamt $2 n \log(n)$ Vergleiche (ohne den Heap zu bauen). Dies absolut ohne Extraplatz! Ein Wermutstropfen (z.B. gegenüber dem Mergesort, das wir noch sehen werden) ist der Faktor $2$, dazu unten mehr.

**Wieviele Bewegungen machen wir?**
Entlang eines Versickerpfades machen wir maximal $\log n$ Vertauschungen. Somit ist die Anzahl Bewegungen auch in $\O(n \log n)$.

**Wieviel kommt noch dazu beim Bauen des Heaps?**
Wir rufen versickern $\frac{n}{2}$ mal auf, also höchstens $\O(n\log n)$. Aber wenn man genauer hinschaut, sieht man, dass unsere Versickerungspfade oft viel kürzer sind: Für die Knoten an Position $\frac{n}{4}$ bis $\frac{n}{2}$ ist der Pfad höchstens $1$ lang, für $\frac{n}{8}$ bis $\frac{n}{4}$ höchstens $2$ usw. Erst für die Wurzel kann es $\log n$ werden.
Wenn wir das so aufsummieren, kommt heraus, dass das Herstellen des Heaps sogar in linearer Zeit geht:

$$\begin{align}&\frac {n}{2} \cdot 1 + \frac{n}{4} \cdot 2 + \frac{n}{8} \cdot 3 + \dots\\
=& \left( \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots \right) +
\left( \frac{n}{4} + \frac{n}{8} + \frac{n}{16} + \dots \right) +
\left( \frac{n}{8} + \frac{n}{16} + \frac{n}{32} + \dots \right) + \dots\\
=& n + \frac{n}{2} + \frac{n}{4} + \dots \leq 2n \in \O(n).\end{align}$$

Das Phänomen, das wir hier ausnutzen: Fast alle Knoten eines Baumes sind Blätter oder sehr weit unten im Baum. Nur sehr wenige Knoten haben einen logarithmisch langen Versickerungspfad, sodass die Versickerungslänge *im Schnitt* konstant ist..

Total: $\O(n \log n)$ Vergleiche und Bewegungen.

### Bottom-Up Heapsort
Ein Wermutstropfen beim Heapsort ist der Umstand, dass wir zwei Vergleiche brauchen, um den Schlüssel um eine Ebene zu versickern. Was wir aber sehen können: Schon nach dem ersten Vergleich (Vergleich der beiden Kinder) wissen wir, ob der Schlüssel, falls er versickert, nach links oder rechts versickert. Mit dieser Beobachtung können wir den gesamten potentiellen "Versickerpfad" des Schlüssels finden, ohne den Schlüssel selbst zu kennen. Daher können wir zuerst diesen Weg finden in $\log(n)$ Vergleichen. Anschliessend können wir die Position des Schlüssels auf diesem Weg in $\log(\log(n))$ Vergleichen mittels binärer Suche finden.

Statt in $2\log(n)$ geht es also auch in $\log(n) + \log(\log(n))$ Schritten.

Weitere Idee: Drei Viertel aller Knoten sind auf den untersten zwei Ebenen. Das heisst, wenn wir auf dem Versickerpfad den Knoten suchen, dann landen wir fast immer ganz unten. Darum ist es eine gute Idee statt der binären Suche auf dem Versickerpfad einfach von hinten an linear zu suchen und fast immer werden wir sehr schnell fündig. Dies nennt man *Bottom-Up Heapsort*.

Es gibt Leute, die sagen, dass Bottom-Up Heapsort für grosse Datenmengen sehr schnell ist, schneller als Mergesort, das wir noch sehen werden.

Eine häufige Kritik an Heapsort ist aber seine schlechte Lokalität. Das Ablaufen eines Pfades entspricht einem wilden Umherhüpfen im Array, was es in der Praxis verlangsamt, da Caching nicht gut funktioniert. Mergesort wird hier viel lokaler sein.