# 7 Sortieren in Spezialfällen und Wörterbüchern

[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

Erinnern wir uns daran, was wir bei Quicksort gesehen haben:
- *best case*: Bei gleichmässigem Halbieren gibt es einen Rekursionsbaum der Höhe $\log n$ mit insgesamt $\O(n \log n)$ Vergleichen.
- *worst case*: $\O(n^2)$ Vergleiche, weil wir immer nur eine Element abspalten und das geschieht erst noch bei der schon sortierten Eingabe.
- *average case*: Wir erhalten $\O(n \log n)$, wenn wir über alle Eingaben mitteln oder wenn wir den Pivot randomisiert wählen und dann den Erwartungswert betrachten.

Bevor wir uns noch weitere Sortierverfahren anschauen, wollen wir uns mal kurz besinnen und fragen, wie lange wir dieses Optimierungsspiel noch weiterspielen können. Wie schnell kann ein Sortierverfahren überhaupt sein?

## Untere Schranke mit Entscheidungsbaum
Wir möchten eine untere Schranke, die für jeden Sortieralgorithmus gilt. Wir wollen also zeigen, dass für das Sortierproblem eine bestimmte Anzahl an Vergleichen mindestens notwendig sind für jeden erdenklichen, vergleichsbasierten Sortieralgorithmus.

Die einzige Einschränkung ist also: Wir gehen davon aus, dass der Algorithmus nichts macht ausser Schlüsselvergleiche. Wir wollen also nicht Verfahren anschauen, bei denen wir mit den Schlüsseln mehr machen können, als sie untereinander zu vergleichen, z.B. sie miteinander zu verrechnen oder quasi in die Schlüssel hineinzuschauen. Aber alle Verfahren, die wir bis jetzt gesehen haben, waren auch so - rein vergleichsbasiert.

Wir nehmen als Eingabe eine Schlüsselmenge $a_1, a_2, a_3, \dots, a_n$ und geben als Ausgabe eine Permutation dieser Schlüsselmenge zurück, also zum Beispiel $a_n, a_4, a_{17}, \dots$.

Ein korrektes Sortierverfahren muss jede mögliche Permuatation erzeugen können, denn wir können jede Permutation als Ausgabe erzwingen indem wir den Schlüsseln zum Beispiel entsprechende ganzzahlige Werte von $1$ bis $n$ zuordnen. Wenn wir ein Sortierverfahren generieren, welches dies nicht macht, d.h. eine gewisse Permutation nie erzeugen kann, so kann dieses Verfahren nicht korrekt sein. Die Anzahl der möglichen Permutationen auf $n$ Elementen ist $n! = n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1$.

Wir können uns ein Sortierverfahren als *Entscheidungsbaum* vorstellen. Wir beginnen oben und notieren in jedem Knoten den Schlüsselvergleich, den wir durchführen. So kann ein Verfahren zum Beispiel mit dem Vergleich *"Ist $a_3$ kleiner als $a_7$?"* starten. Je nach dem ob die Antwort *Ja* oder *Nein* ist, fahren wir in einem der beiden darunterliegenden Teilbäume fort. Wir gehen so Ebene für Ebene den Baum hinunter und enden in einem Blatt. Dort müssen wir dann die korrekte Permutation kennen. Ein solcher Entscheidungsbaum braucht also mindestens $n!$ Blätter. Im Bild unten sind die $n!$ möglichen Ausgänge durch die Kästchen mit der Aufschrift $\pi_1$ bis $\pi_{n!}$ illustriert.


Die Laufzeiteigenschaften eines Sortierverfahrens können wir so aus seinem Entscheidungsbaum ablesen.
Die Anzahl Vergleiche eines Sortiervorganges ist dann die Anzahl besuchter Knoten auf dem Weg durch den Entscheidungsbaum. Im schlimmsten Fall besuchen wir das tiefste Blatt und im besten Fall das oberste Blatt, das am nächsten bei der Wurzel liegt. Wenn wir die mittlere Laufzeit bestimmen möchten, können wir dazu die mittlere Blatttiefe des Entscheidungsbaumes bestimmen. So eine Blatttiefen-Analyse kommt uns von der binären Suche her bekannt vor.

Wir wissen, dass der Entscheidungsbaum $n!$ Blätter hat. Wir sind nun an der mittleren Tiefe (als *Tiefe* bezeichnen wir den Abstand von der Wurzel) eines Blattes in einem Baum mit $n!$ Blättern interessiert.


Wir behaupten, dass die mittlere Tiefe $mtb(b)$ eines Baumes mit $b$ Blättern mindestens $\log_2(b)$ ist und beweisen dies mit Induktion und mittels Widerspruchsbeweis:

*Behauptung*: $mtb(b) \ge \log_2(b)$
*Verankerung*: $mtb(2) \ge 1 = \log_2(2)$


Wählen wir das kleinste $b$, sodass $mtb(b) < \log_2(b)$ und sei $T$ ein solcher Baum mit $b$ Blättern. Wir bezeichnen mit $T_l$ den linken und $T_r$ den rechten Teilbaum der Wurzel. Wir wissen, dass $mtb(b) = \frac{1}{b} ( (mtb(b_l)+1)b_l + (mtb(b_r)+1)b_r)$, wobei $b_l$ und $b_r$ die Anzahl der Blätter im linken und im rechten Teilbaum $T_l$ und $T_r$ sind. Da $b_l < b$ und $b_r < b$ gilt, folgt dann

$$\begin{align}
mtb(b) &\geq \frac{1}{b}\cdot (\log (b_l + 1)\cdot b_l + \log(b_r + 1)\cdot b_r)\\
&\geq \frac {1}{b}\cdot \left(\log\left(\frac{b}{2} + 1\right)\cdot \frac{b}{2} + \log\left(\frac{b}{2} + 1\right)\cdot \frac{b}{2}\right)\\
&= \frac {1}{b}\cdot \left(\log\left(\frac{b}{2} + 1\right)\cdot \frac{b}{2} \cdot 2\right)\\
&= \frac {1}{b}\cdot \left(\log\left(b\right)\cdot b\right)\\
&=\log_2(b),
\end{align}$$
ein Widerspruch zur Annahme, dass $mtb(b) < \log_2(b)$. In der zweiten Ungleichung benutzen wir dabei, dass $b = b_l + b_r$ gilt und die Funktion $f(x) = x\log x + (1-x)\log(1-x)$ ihr Minimum bei $x= \frac{1}{2}$ erreicht und wir somit die durchschnittliche Blatttiefe bei gleichgrossen Teilbäumen minimieren.

Wir wissen nun, dass der Entscheidungsbaum $n!$ Blätter hat. Es gilt $(n/2)^{n/2} < n! = n\cdot (n-1)\cdot (n-2)\cdots 2 < n^n$. Somit ist $\log(n!) \in \Theta(n \log n)$ und Sortieren dauert mindestens $\Omega(n \log n)$ Schritte, *egal* welchen Algorithmus mit Schlüsselvergleichen wir verwenden. Auch in der Zukunft wird also niemand einen besseren Algorithmus erfinden.

## Sortieren in Linearzeit

Nun wollen wir unseren Beweis gleich selbst relativieren und die $n \log n$-Schranke durchbrechen indem wir mit den Schlüsseln nicht nur vergleichen sondern sie genauer anschauen.

Stellen wir uns vor, wir wissen bereits im Vorfeld, dass die Schlüssel einfach die Zahlen von $1$ bis $n$ sind. Dafür gibt es ein ganz einfaches Sortierverfahren: Sehen wir an erster Stelle den Schlüssel $i$, so können wir ihn direkt an Stelle $i$ hintauschen, denn wir wissen, dass dieser Schlüssel am Ende dort zu liegen kommt. Somit können wir ein Element nach dem anderen direkt an sein Ziel tauschen und sind nach $n$ Schritten fertig.

### Bucketsort
Sind die Schlüssel ganze Zahlen oder allgemein aus einem beschränkten Universum, so können wir ebenfalls etwas besseres tun. Nehmen wir an, wir haben nur zehnstellige Zahlen. Zum Beispiel tausend zehnstellige Zahlen. Wir schauen uns zuerst nur die ersten drei Stellen an und sortieren die Zahlen in entsprechende Gruppen, sogenannte *Buckets*, ein. Die Zahl $8392709235$ kommt beispielsweise in den Bucket $839$. In jedem dieser Buckets landen dann hoffentlich nur noch wenige Zahlen, die wir naiv, z.B. mit Bubble Sort sortieren können. Anschliessend bekommen wir die sortierte Folge ganz leicht indem wir der Reihe nach durch die $1000$ Buckets gehen. Dieses Verfahren heisst *Bucketsort* (Surprise, surprise!). Für zufällige Schlüssel und genügend viele Buckets, kann man zeigen, dass dies im Erwartungswert gut geht, also in *jedem* Bucket nur wenige Schlüssel landen und damit Bucketsort auch linear läuft. Diese Analyse machen wir hier aber nicht.

### Sortieren durch Fachverteilen (Radixsort)

Ein weiteres Verfahren, das Bucketsort quasi wiederholt anwendet, ist das Sortieren durch Fachverteilen, englisch Radixsort. Es wurde zum Beispiel früher zum Sortieren von Lochkarten genutzt und wird auch heute noch zum Sortieren von Briefen nach Postleitzahl genutzt.^[Siemens vertreibt beispielsweise solche gigantische Briefsortiermaschinen, wie [diese hier](http://goo.gl/Saig3Q), welche einen mehrstufigen Sortiervorgang unterstützen.]

Nehmen wir als Beispiel die Schlüssel: $17, 04, 64, 19, 27, 34, 12$, wobei wir bereits die $4$ mit einer führenden Null auf eine einheitliche Länge gebracht haben.

Die Idee ist nun, die Zahlen Ziffer für Ziffer zu betrachten, daher auch der Name *Radix* (lateinisch *Wurzel*), nach der *"Wurzel"* des Zahlensystems.

#### Radix Sort MSD
So teilen wir die Zahlen gemäss ihrer führenden Ziffer in eine von $10$ Schubladen ein. In jedem der $10$ Buckets sortieren wir die Zahlen dann rekursiv nach dem selben Verfahren, beginnend mit der zweithöchsten Ziffer.

In unserem Beispiel erhält nur ein Bucket mehr als einen Schlüssel: der erste Bucket enthält $17$, $19$ und $12$. Diese drei Schlüssel sortieren wir dann rekursiv, wie hier gezeigt.


Da wir bei diesem Verfahren mit der führenden Ziffer beginnen, nennt man dieses Verfahren *MSD Radix Sort* (für *Most Significant Digit*). In der Praxis macht man das natürlich nicht unbedingt im Zehnersystem, sondern eher im Binärsystem, wir schauen uns also Bit für Bit an.

Für dieses Verfahren brauchen wir also Zugriff auf die einzelnen Ziffern der Schlüssel und wir nehmen an, dass Zugriff auf die Ziffern die konstante Kosten haben. Die Anzahl der Fächer hängt von der Art der Schlüssel ab. Falls wir z.B. Buchstaben und Wörter sortieren wollen, dann benötigen wir $26$ Fächern, für Binärzahlen genügen $2$ Fächer.

Für die Implementierung müssen wir uns auch überlegen, wie wir das genau machen mit dem Fachverteilen. Wir wissen ja nicht im Voraus wie viel in jedem Fach landen wird. Wir können jedes Fach als Liste implementieren und den Platz dafür vorzu allozieren aber es gibt einen einfachen Trick, der dies erübrigt: Wir können in einem ersten Durchgang auszählen wie gross jedes Fach sein muss. Dann legen wir ein einzelnes Array der gesamten Länge $n$ an und reservieren darin für jedes Fach gleich die passenden Abschnitte.

Die Anzahl Sortierschritte hängt nun von der Länge der Zahl ab. Sei dazu $n$ die Anzahl Zahlen, $l$ die Länge jeder Zahl und $m$ die Ziffervorratsgrösse (also die Anzahl verschiedener Ziffern die es gibt). Wenn wir $l$ Ziffern haben, dann läuft das Verfahren in $\O((n+m)\cdot l)$ Schritten. Wenn die Zahlen eher klein sind, also $l$ kleiner ist als $\log n$, dann machen wir so Zeit gut gegenüber den klassischen Sortierverfahren in $\O(n \log n).

#### Radix Sort LSD
Nehmen wir nochmals das gleiche Beispiel, verteilen wir aber zuerst nach der letzten Ziffer auf die Fächer auf:

Die Eingabe $17, 04, 64, 19, 27, 34,12$ ergibt folgende Fachverteilung

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|----|---|---|----|---|----|
| | |12 | | 04 | | | 17 | | 19 |
| | | | | 64 | | | 27 | | |
| | | | | 34 | | | | | |

Danach sammeln wir die Zahlen von links nach rechts ein: $12, 04, 34, 64, 17, 27, 19$. Diese Folge ist nun noch ganz und gar nicht sortiert, aber ein wenig Struktur ist bereits erkennbar. Im zweiten Schritt gehen wir nun durch diese Sequenz und sortieren sie nach der linken Ziffer in die Fächer ein.

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|----|----|----|---|---|----|---|---|---|
| 4 | 12 | 27 | 34 | | | 64 | | | |
| | 17 | | | | | | | | |
| | 19 | | | | | | | | |

Nun haben wir die Schlüssel sortiert vor uns: $04,12,17,19,27,34,64$.

Warum funktioniert das? Das Einsammeln und Neuverteilen führt dazu, dass die Vorsortierung nach der hintersten Ziffer beim Sortieren nach der zweithintersten Ziffer erhalten bleibt.

Und auch das lässt sich wieder leicht implementieren. Entweder durch das Anlegen solcher Listen oder durch das Auszählen der Korbgrössen, wie wir vorher gesehen haben.

Die Laufzeit ist erneut $\O((n+m) \cdot l)$ und wir kommen gar ohne Rekursion aus.

## Abstrakte Datentypen

### Einleitung: Wörterbuch

Bis jetzt haben wir uns darauf beschränkt, Schlüssel zu suchen und wir haben gesehen, dass wir das schnell können, wenn die Schlüssel sortiert sind. Nun will man aber eigentlich auch Schlüssel hinzufügen und löschen können.

Ein *abstrakter Datentyp* ist eine Beschreibung von Daten und den verschiedenen darauf anwendbaren Operationen (eben z.B. Einfügen, Löschen, Suchen, usw.). Eine Implementierung eines abstrakten Datentyps nennt man *Datenstruktur*.

Wenn man von Efiizienz von den Datenstrukturen spricht, dann soll man Bescheid geben, ob *eine Folge von Operationen* möglichst günstig sein soll, oder die Laufzeit einer *Einfügen*-Operation, einer *Entfernen*-Operation usw. angeben.

Wollen wir beispielsweise nur *Einfügen* und *Löschen* unterstützen, ohne irgendwelche Abfragen, lässt sich das trivial in konstanter Zeit pro Operation mittels maximaler Faulheit implementieren. Bei einer *Einfüge*-Operation sagen wir einfach *"Ja, erledigt"*, tun aber gar nichts und ebenso fürs *Entfernen*. Da der Benutzer der Datenstruktur nie was über den aktuellen Zustand erfahren kann, müssen wir uns auch nichts merken.

Spannend wird es erst, wenn wir auch *Suchen* unterstützen wollen, oder wenn die *Einfüge*-Operation auch zurückgibt, ob der Datensatz schon da war, oder wenn wir beim *Entfernen* antworten, ob der Datensatz überhaupt vorkam.

Wir sind nun an Datenstrukturen für einen abstrakten Datentyp interessiert, der die Operationen *Einfügen*, *Löschen* und *Sortieren* umfasst, interessiert. Eine Datenstruktur, die diesen abstrakten Datentyp implementiert, nennt man, etwas unmotiviert, *Wörterbuch*-Datenstruktur. Wir schauen uns nun an, wie man so ein *"Wörterbuch"* implementieren kann.

### Array als Wörterbuch
Die einfachste Implementierung eines Wörterbuches gelingt uns mit einem Array, das wir fortlaufend sortiert halten. Suchen kostet uns mittels binärer Suche $\O(\log n)$, Einfügen kostet $\O(n)$ (wir müssen einen Platz freischaufeln und dafür viel verschieben), und Entfernen kostet uns ebenfalls lineare Zeit. Die langsamste Operation ist also in $\O(n)$ - keine wirklich gute Garantie.

Bringt uns die Sortierung was? Wenn wir das Array unsortiert halten, dann ist das *Einfügen* trivial (wir hängen in konstanter Zeit hinten an), aber die *Suche* und das *Entfernen* dauert dann lineare Zeit.

Wir tauschen also eine lineare Operation gegen eine andere, aber eigentlich würden wir doch gerne alles in logarithmischer Zeit erledigen. Ein Array erfüllt unsere Anforderungen also weder sortiert noch unsortiert.

### Lineare Liste als Wörterbuch
In einer sortierten lineare Liste zu *Suchen*, *Einfügen* und zu *Entfernen* kostet uns je lineare Zeit $\O(n)$.


Bei einer linearen Liste wird ein Element mit einem Zeiger mit seinem Nachfolger verbunden. Im Unterschied zu einem Array können wir nicht mehr auf jeden beliebigen Eintrag in konstanter Zeit zugreifen, sondern müssen den Zeigern folgen, bis wir auf das gesuchte Element treffen.

Wenn wir bereits wüssten wo in der Liste wir eine Element einfügen oder löschen möchten, so könnten wir in konstanter Zeit, indem wir die Zeiger entsprechend verbiegen. Für die Suche wird aber lineare Zeit benötigt, selbst wenn die Liste sortiert wird, da wir ja den Zeigern folgen müssen und nicht direkt auf beliebige Elemente in der Liste zugreifen können. Damit benötigt auch das Löschen lineare Zeit (egal ob sortiert oder nicht). Falls wir beim Einfügen zusätzlich prüfen wollen, ob das Element bereits vorhanden ist, dann benötigt auch diese Operation lineare Zeit in unsortierten Listen.

### Skipliste als Wörterbuch
Unser *Traum* ist nach wie vor unerfüllt: $\O(\log n)$ für alle drei Operationen.

Eine weitere Idee ist es, die sortierte Liste mit zusätzlichen Zeigern auszustatten, sodass wir weit umherspringen können und so eine binäre Suche erlauben können. Skizziert für sieben Elemente sieht das so aus:


Dieses Zeiger-Konstrukt nennt man *Skipliste*, eben weil man weite Distanzen *skippen* kann. Wir sagen eine Skipliste hat die *Höhe* $\log n$ und meinen damit, dass jedes Element höchsten $\log n$ Einträge hat.

Das *Suchen* in einer Skip-Liste kostet uns wie gesagt $\O(log n)$, da uns die Zeiger ermöglichen die binäre Suche durchzuführen. *Einfügen* und *Entfernen* ist nun aber immer noch $\O(n)$, da wir die Elemente zwar schnell finden, aber dann viel Arbeit haben, um die Zeigerstruktur zu erhalten.


### Randomisierte Skipliste als Wörterbuch
Wie erhalten wir eine ähnliche Zeigerstruktur effizient? Wir lassen die Skip-Zeiger nicht genau in die Mitte, genau in einen Viertel etc. zeigen sondern, wir entscheiden randomisiert, wie viele Links ein Element braucht.

Wir werfen dazu nach dem Einfügen eines neuen Elementes eine Münze, die uns sagt, ob wir noch einen weiteren Zeiger hinzufügen sollen oder nicht. Zeigt die Münze Kopf, fügen wir einen weiteren Link ein und teilen dazu den vorhergehenden Zeiger auf dem gleichen Level, der das neue Element überspannt, entsprechend auf. Dies wiederholen wir so lange bis die Münze einmal Zahl zeigt. Somit hat das durchschnittliche Element nur wenige Skip-Links, aber ein paar Element erlauben uns weiterhin weit zu springen.

Die Analyse und Implementierung lassen wir hier weg, uns geht es nur um die Idee. Die Essenz ist, dass wir, in bester Binärsuchtradition, weiterhin über viele Elemente hinwegspringen können wollen und dies erreichen wir auch mit der folgenden Datenstruktur.

### Suchbaum als Wörterbuch

Ein Suchbaum ist ein Baum mit den Schlüsseln in den Knoten, der folgende Bedingung erfüllt: Die Schlüssel im linken Teilbaum sind immer kleiner als die Wurzel und die Schlüssel im rechten Teilbaum sind immer grösser als die Wurzel. Diese Bedingung soll für jeden Teilbaum gelten.


So einen Baum kann für die Suche sehr gut verwendet werden: Wir beginnen bei der Wurzel und vergleichen den dort gespeicherten Schlüssel mit dem gesuchten Schlüssel. Dann wissen wir, ob wir nach rechts oder nach links gehen müssen (oder den Schlüssel bereits gefunden haben). Dasselbe machen wir dann für den entsprechenden Teilbaum, bis wir an ein Blatt gelangen oder den Schlüssel gefunden haben. Sind wir an einem Blatt angekommen, ohne den Schlüssel gefunden zu haben, so können wir sicher sein, dass der Schlüssel nicht im Baum gespeichert ist.

Wenn wir uns an den Heap erinnern, sehen wir, dass dieser Baum eine strengere Bedingung erfüllt. Dadurch können wir in so einem binären Suchbaum suchen, während das in einem Heap nicht so einfach und schnell möglich ist.

Bevor wir uns Gedanken dazu machen, wie wir einen Suchbaum bauen und verwalten, wollen wir uns (ähnlich wie letzte Woche beim Sortieren) überlegen, wie wir denn einen gültigen Suchbaum erkennen können.

#### Suchbaum testen durch Traversierung

Wir können die Gültigkeit eines Suchbaumes $T$ überprüfen indem wir ihn rekursiv durchlaufen, eine sogenannte *Traversierung* durchführen. Wenn wir dabei alles links vor und alles rechts nach der Wurzel ausgeben, so sollten wir die sortierte Folge der Schlüssel erhalten. Andernfalls wissen wir, dass der Suchbaum nicht die gewünschte Eigenschaft hat. Dies nennt man

**Inorder-Traversierung** (deutsch: Symmetrische Reihenfolge).

spucke T aus:
	falls T nicht leer
		spucke T.links aus
		zeige Schlüssel der Wurzel
		spucke T.rechts aus

Im Beispiel kommt so $3,11,18,25,27,34,39$ raus.

Statt die Wurzel in der Mitte auszugeben, können wir das auch anders machen. Auch diese beiden Varianten haben spezielle Namen:

**Preorder-Traversierung** (deutsch: Hauptreihenfolge)

preorder(T)
	- Wurzel
	- preorder(T.links)
	- preorder(T.rechts)

Im Beispiel: $25,11,3,18,34,27,39$.

**Postorder-Traversierung** (deutsch: Nebenreihenfolge)

postorder(T)
	- postorder(T.links)
	- postorder(T.rechts)
	- Wurzel

Im Beispiel: $3,18,11,27,39,34,25$.