Quicksort: Unterschied zwischen den Versionen

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 in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40).  

Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf unser Vorwissen (Indikatorvariablen und Harmonische 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>, wobei <math>z_i < z_j</math>) im Laufe des Algorithmus direkt miteinander verglichen werden?''

* Sind die Daten völlig zufällig verteilt, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot gewählt zu werden. Damit <math>z_i</math> und <math>z_j</math> verglichen werden, muss exakt <math>z_i</math> oder <math>z_j</math> der "Gewinner" dieser Ziehung sein. Da es <math>2</math> günstige Fälle (<math>z_i</math> oder <math>z_j</math>) bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.

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

Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder! 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 (stark vereinfacht) <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.  

Da konstante Vorfaktoren wie die <math>2</math> 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>.

Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente.  

Der Aufwand für das Vergleichen (Partitionieren) einer Ebene mit <math>n</math> Elementen ist proportional zu <math>n</math>. Nennen wir diesen Aufwand <math>c \cdot n</math> (wobei <math>c</math> eine Konstante für die Dauer eines Vergleichs ist).

Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.

Da in der asymptotischen Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.