Herzlich willkommen!

Unser Thema lautet weiterhin Sortieren.

Wir haben letztes Mal gesehen, eine untere Schranke dafür, wie viele Vergleiche ein Sortieralgorithmus mindestens braucht, um korrekt zu arbeiten.

Die grobe Antwort war N mal log N.

Wir sehen uns heute einen weiteren Algorithmus an, den Sie sicher auch alle kennen.

Das ist QuickSort.

Wir hatten vorher gesehen MergeSort. MergeSort war ein Divide-and-conquer-Algorithmus, der in worst-case-Zeit N log N lief.

QuickSort hat diese angenehme Eigenschaft nicht.

Das kann man sich schnell klar machen, was passiert, wenn man die Pivotelemente schlecht wählt. Das sehen wir uns nachher noch genauer an.

QuickSort ist dafür aber ein erstes nicht triviales Beispiel eines Algorithmus, in dem wir eine average-case-Analyse hinbekommen, die besser ist als der worst-case.

Bisher haben wir zwar average-case-Analysen gesehen, aber das waren alles Spielzeugbeispiele, so etwas wie einen Counter-Inkrementieren.

Jetzt haben wir also mit QuickSort hier einen ernsthaften Algorithmus, für den wir ebenso eine average-case-Analyse auch hinbekommen.

Im Allgemeinen sind average-case-Analysen schwerer als worst-case-Analysen.

Weil das ein relativ ernsthafter Algorithmus ist, wird das Argument nicht ganz so stark durchformalisiert sein.

Es wird also viel Text an der Tafel stehen.

Das vergleicht sich dann stilistisch recht schön mit dem, was wir letztes Mal gemacht haben, als wir nun gezeigt haben, dass dieser Baum von Vergleichen,

der unser Hauptargument war für die untere Schranke, mindestens so viele Blätter hat wie Permutationen.

Das ist nun geradezu so, wie ich das letztes Mal gemacht habe, selbst Kritik muss man auch mal üben, fast ein Beispiel einer Überformalisierung.

Ich will Ihnen das im Nachhinein beim Nacharbeiten verdaulich erscheinen, noch mal ein kurzes Argument geben, das vielleicht verständlicher ist.

Ich erinnere an das Hauptlemma.

So, jetzt viel Notation, aber dafür kurz. Zur Erinnerung, B von Pi 1 war praktisch die Antwort des Algorithmus, wenn wir die Permutation der Zahlen 1 bis n Pi 1 rein tun, ebenso Pi 2.

Was das Lemma sagt, ist, dass wenn auf zwei Permutationen dieselbe Antwort kommt, dass dann schon dieselben Permutationen waren.

Der Beweis war, na lang war er nicht, aber er verlangte etliches an Begrifflichkeit aus dem Bereich Permutationen und ihre Inversen etc.

So, jetzt wollen wir mal einen etwas waghalsigen Beweis hinschreiben.

Und der lautet offensichtlich.

Selbstverständlich muss ein korrekt arbeitender Sortieralgorithmus zwei verschiedene Permutationen der Zahlen 1 bis n, die ich ihm vorwerfe, unterschiedlich behandeln.

Sonnenklar, ja? Fertig.

So ähnlich wird es heute auch weiter abgehen.

Ja, QuickSort.

Wie angekündigt, ist ebenfalls ein Divide-and-Conquer-Algorithmus.

MergeSort hat sich beim Divide relativ simplizistisch angestellt sofort und beim Divide einfach die Liste in der Mitte durchgehauen.

Dafür ist dann das Conquer schwer, nämlich das Merge, da müssen zwei sortierte Listen, von denen nicht klar ist, wie die sich überlappen, miteinander verzwirbeln.

QuickSort geht da anders vor, da oben war eine Zwischenfrage.

Sind Pi das Elemente?

Nein, Permutationen.

Also es war gefragt, was hier das Pi ist. Nicht nochmal, das Pi ist eine Permutation, also Pi 1, Pi 2 aus Sn.

Also zwei Permutationen, das zahlen 1 bis n.

So, also Divide-and-Conquer.

So, und wir teilen jetzt nicht bei QuickSort wie bei MergeSort in eine vordere und eine hintere Hälfte, sondern wir teilen in

in kleine, in große und in mittelgroße Elemente.

Und dazu brauchen wir irgendeine Methode zu entscheiden, was nun klein, was groß und was mittelgroß ist.

Das heißt, wir wählen ein Element P, ein Element P aus der Sequenz.

Ich verwende jetzt, das ist Teil der neuen Saloppheit, ja, ich verwende jetzt Elementschreibweise für Sequenzen.

Ich meine, eigentlich ist natürlich das Elementsymbol reserviert für Mengen.

Aber es ist wiederum klar, was das heißt hier. Also P kommt in der Liste irgendwo vor.

So.

Dieses P heißt das Pivoelement und wir unterteilen eben die Liste in solche Elemente, die echt kleiner sind als das Pivoelement,

die gleich sind in Anführungsstrichen dem Pivoelement und die größer sind dem Pivoelement.

Das mit dem Gleich, das kann man jetzt also unterschiedlich durch formalisiert handhaben.

Bei Gleich stellen wir uns also jetzt vor, die Elemente hätten Schlüssel,