/ Algorithmen & Komplexität

Quick Sort Vergleiche (Average)

Durchschnittliche Anzahl Vergleiche beim Quick Sort: Vergleiche ≈ 1,39 · n · log₂(n). Im Worst Case (schlechter Pivot) entartet er zu O(n²).

01 · Eingabe

Quick Sort Vergleiche (Average) berechnen

Durchschnittliche Anzahl Vergleiche beim Quick Sort: Vergleiche ≈ 1,39 · n · log₂(n). Im Worst Case (schlechter Pivot) entartet er zu O(n²).

Vergleiche = 1,39 · n · log₂(n)

n Elementanzahl

Worum geht es?

Quick Sort wählt ein Pivot-Element, partitioniert die Eingabe und sortiert die beiden Hälften rekursiv. Im Average Case mit zufälligem Pivot ergibt die Analyse ≈ 1,39 · n · log₂(n) Vergleiche — der Faktor 1,39 ≈ 2 · ln 2 stammt aus der erwarteten Pivot-Unwucht.

Fall	Vergleiche	Bemerkung
Best Case	n · log₂(n)	Pivot teilt exakt mittig
Average	≈ 1,39 · n · log₂(n)	zufälliger Pivot, randomisiert
Worst Case	n · (n − 1) / 2	Pivot stets minimal/maximal

In der Praxis ist Quick Sort meist schneller als Merge Sort, weil er in-place arbeitet und cache-freundlich ist — sofern eine vernünftige Pivot-Strategie (Median-of-Three, Introsort) den Worst Case vermeidet.

Die Formel

Formel Quick Sort (Average)

Vergleiche = 1,39 · n · log₂(n)

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
n	Elementanzahl	—	Anzahl zu sortierender Elemente.
Vergleiche	Vergleiche	—	Durchschnittliche Anzahl Vergleiche.

Minimal-Beispiel

n = 1024:

Rechnung Vergleiche

Vergleiche = 1,39 · 1024 · log₂(1024)
           = 1,39 · 1024 · 10
           ≈ 14 234

Praxis-Beispiele

Beispiel 1 — n = 10⁶

Rechnung n = 10⁶

Vergleiche = 1,39 · 1 000 000 · 19,93
           ≈ 27 700 000

Beispiel 2 — Vergleich Merge vs. Quick

n = 10⁶:

Rechnung Vergleich

Merge:  1,0 · 10⁶ · log₂(10⁶) ≈ 1,99 · 10⁷
Quick:  1,39 · 10⁶ · log₂(10⁶) ≈ 2,77 · 10⁷

Quick: ca. 39 % mehr Vergleiche im Average.

Beispiel 3 — Worst-Case-Falle

n = 1000, bereits sortiert, naives Pivot = erstes Element:

Rechnung Worst Case

Vergleiche = 1000 · 999 / 2
           = 499 500

(statt 1,39 · 1000 · log₂(1000) ≈ 13 850)