Sortieren und Suchen

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? [1]

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.

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?

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 evtl. 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)$. Wenn man genauer hinschaut, kann man gar zeigen, dass es nur $\O(n)$ ist.

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

Einfügen

Um alle Operationen einen Priority Queue, nämlich “Maximum extrahieren” (aus einem Max-Heap) und “Einfügen eines neuen Elementes” zu unterstützen, fehlt uns noch das Einfügen. Das ist ganz einfach: Wir vergrössern den Array um eine Position, schreiben dort das neue Element hin und stellen danach die Heapbedingung wieder her indem wir das Element so lange wie nötig “hochblubbern” lassen.

Einfügen(x)
    // Neues Element anhängen:
    n := n+1
    A[n] = x
    // Hochblubbern lassen:
    i := n
    while i > 1 and A[i/2] < A[i]
        swap(A[i/2], A[i])
        i := i/2

Das Einfügen dauert also höchstens so lange wie der Heap hoch ist, also $\O(\log n)$.

Aufgabe (C++ Vorlage hier)

Eure erste Aufgabe ist es nun einen solchen Max-Heap mit den Operationen Insert und ExtractMax zu implementieren.

Suchen

Suche (ab Knoten p nach Schlüssel k)
    if p null then erfolglos
    else if k < key von p then suche(links von p, k)
    else if k > key von p then suche(rechts von p, k)
    else gefunden

Unser Wunsch an die Laufzeit für diesen Suchbaum war $\O(\log n)$. Das können wir auch erreichen, wenn wir den Baum statisch aufbauen können, sich die Schlüsselmenge also nicht dynamisch ändert. Wir bauen den Baum balanciert (so wie beim Heap für Heapsort) und erreichen so logarithmische Höhe.

Wir wollen das jetzt dynamisch machen, also auch Einfüge- und Löschoperationen unterstützen. Die natürlichste Art die Einfügeoperation zu unterstützen ist die folgende:

Einfügen

Einfügen(k)
    Suche ab der Wurzel nach k
    Finden wir k im Baum, müssen wir nichts einfügen
    Sonst, landen wir in einem Blatt p
    Ersetze das Blatt durch einen neuen Knoten mit dem Schlüssel k,

Erreichen wir damit logarithmische Laufzeit? Im schlechtesten Fall leider nicht. Wenn wir in einen leeren Baum die Schlüssel $1,2,\dots,n$ der Reihe noch einfügen, dann degeneriert der Suchbaum zu einer linearen Liste mit linearer Tiefe. Also: Worst Case $\Theta(n)$.

Ist es wenigstens im Mittel gut? Für zufällige Eingabereihenfolgen kann man argumentieren, dass wir eine mittlere Suchbaumhöhe von $\Theta(\log n)$ erreichen.

Entfernen

Wie können wir Schlüssel entfernen? Es genügt nicht, den entsprechenden Knoten zu finden und zu löschen, da wir dabei auch alle Schlüssel in seinen Teilbäumen verlieren. Zusätzlich müssen wir vorsichtig sein, dass wir die Suchbaumeigenschaft nicht zerstören.

Wir unterscheiden drei Fälle:

Entfernen(k)
    Suche ab der Wurzel nach k
    Endet mit Knoten p mit key(p) = k
    1. Fall: p hat kein Kind -> Knoten einfach löschen
    2. Fall: p hat ein Kind -> lenke Zeiger vom Vater aufs Kind
    3. Fall: p hat zwei Kinder -> der interessante Fall!

Der spannende Fall ist also, wenn der zu löschende Knoten zwei Kinder hat. Wir können ihn dann nicht einfach löschen, da es danach keine einfache Möglichkeit gibt, die beiden darunterliegenden Teilbäume in der verbleibenden Suchbaum einzubetten. Der Trick ist es nun stattdessen ein anderes Element zu löschen, welches nur höchstens ein Kind hat.

Für dieses andere Element interessieren wir uns nun für den Knoten mit dem grössten Schlüssel im linken Teilbaum von $p$. Dies ist der nächstkleinere Wert vor $k$ in der sortierten Folge aller Schlüssel, genannt (symmetrischer) Vorgänger. Das selbe gilt für den kleinsten Schlüssel im rechten Teilbaum, genannt (symmetrischer) Nachfolger.

Warum können wir sicher sein, dass die nächstkleineren und grösseren Schlüssel in der global sortierten Folge wirklich immer im Teilbaum von $p$ liegen? Die sortierte Reihenfolge entspricht der Inorder-Traversierung des Suchbaumes. Da beide Kinderteilbäume von $p$ nicht leer sind, stammen also die Schlüssel unmittelbar vor und nach $k$ in der sortierten Folge aus dem Teilbaum von $p$.

Was bringen uns diese Vorgänger und Nachfolger? Der Vorgänger und Nachfolger haben je höchstens ein Kind. Denn hätten sie zwei Kinder, so wären sie in der Traversierung nicht direkt vor/nach $k$. Somit ist das Entfernen dieser Knoten einer der beiden trivialen Fälle.

Entfernen im dritten Fall bei Knoten k:
Finde den sym. Vorgänger;
> gehe ein Schritt nach links,
> gehe solange rechts wir möglich (so erreicht man den sym. Vorgänger)
Tausche k mit sym. Vorgänger
Knipse den sym. Vorgänger ab oder leite von Vater um. (1. oder 2. Fall)

Aufgabe (C++ Vorlage hier)

Eure zweite Aufgabe ist es nun einen natürlichen Suchbaum genau so zu implementieren! (verwende den sym. Vorgänger beim Löschen)

In der Praxis gibt es viele Tricks um den Code zu vereinfachen. Ein cooler Trick ist es statt Blätter mit null Zeigern ins Leere zeigen zu lassen, allozieren wir einen zusätzlichen Knoten auf den alle Blätter zeigen. Bevor wir dann jeweils eine Suche starten, schreiben wir diesen Schlüssel auf diesen zusätzlichen Knoten. Damit wissen wir, dass die Suche immer den Schlüssel finden wird.

Jetzt haben wir also eine Laufzeit von $\O(\text{Höhe})$ erreicht für alle Operationen, falls unser Baum am Anfang leer war! Wie hoch wird dieser Baum? Worst Case: $\Theta(n)$ Best Case: $\Theta(\log n)$

Im Normalfall funktionieren natürliche Suchbäume ganz gut, aber wie immer hätten wir gerne Worst Case Garantien.