Quicksort: Unterschied zwischen den Versionen

== Maximumsuche ==

Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem mathematischen Trick: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu verstehen, analysieren wir einen simplen Code zur Maximumsuche:

Die Vergleiche in der <code>if</code>-Bedingung werden immer <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt überschrieben (Update-Operation)?

Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist exakt 50% (<math>\frac{1}{2}</math>).  

'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.

Der beste Fall liegt vor, wenn das Pivot-Element die Liste immer exakt in der Mitte teilt. Die Teillisten sind dann immer gleich groß.

Wird die Anzahl der zu sortierenden Elemente <math>n</math> verdoppelt, kommt durch die fortlaufende Halbierung lediglich '''eine einzige neue Rekursionsebene''' (ein Baum-Level) hinzu. Dieses Wachstumsverhalten (wie oft kann ich <math>n</math> durch 2 teilen, bis 1 übrig bleibt?) wird mathematisch durch den Logarithmus zur Basis 2 ausgedrückt: <math>\log_2(n)</math>.

Wir haben also insgesamt <math>\log_2(n)</math> Ebenen. Auf '''jeder einzelnen Ebene''' müssen in der Summe <math>n</math> Elemente betrachtet und mit dem jeweiligen Pivot verglichen werden.  

Wir multiplizieren also die Arbeit pro Ebene (<math>n</math>) mit der Anzahl der Ebenen (<math>\log_2(n)</math>).

In der Praxis haben wir selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste beispielsweise im Verhältnis 30:70 oder 60:40.  

Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf das Prinzip der '''Indikatorvariablen''' und der '''Harmonischen Reihe''' zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>) im Laufe des Algorithmus miteinander verglichen werden?''

* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein Element, dessen Wert zwischen den beiden liegt, als Pivot gewählt wird.

* Sind die Daten völlig zufällig verteilt, ist die Wahrscheinlichkeit, dass von <math>k</math> Elementen genau das größte oder kleinste zuerst als Pivot gewählt wird, exakt <math>\frac{2}{k}</math>.

Summieren wir diese Wahrscheinlichkeiten (Erwartungswert) für alle Elementpaare im Array auf, erhalten wir folgende Doppel-Summe:

Setzt man für den Abstand <math>(j - i + 1)</math> eine neue Variable <math>k</math> ein, löst sich die innere Summe auf zu:

Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder, die wir bereits bei der Maximumsuche kennengelernt haben! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert, ergibt die innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.  

Da Konstanten wie der Faktor 2 beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:  

'''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums der harmonischen Reihe sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.