5. Quicksort¶
Überblick¶
- Weiterer Sortieralgorithmus
- Vorteil von Quicksort gegenüber Mergesort: in place, d.h. es wird auf dem laufenden Array gearbeitet und kein zweites Array benötigt (Speicherverbrauch!).
- Asymptotische durchschnittliche Laufzeit ebenfalls $O(n \log n)$
Sortierproblem¶
- Eingabe (Input): Ein Array mit $n$ Zahlen in beliebiger Ordnung
- Ausgabe (Output): Ein Array mit den gleichen Zahlen sortiert aufsteigend beginnend mit dem kleinesten Element.
- Rekursive Partitionierung um ein Pivot Element, solange bis Arraylänge $\leq 1$:
In-place Implemetierung¶
- Kein doppelter Speicherverbrauch.
Quicksort¶
Input: Array $A$ of $n$ distinct integers, left and right endpoints $l,r \in \{1 \dots n\}$
Postcondition: elements of the subarray $A[l], A[l+1] \dots A[r]$ are sorted from smallest to largest
if $l \geq r$ then
return
$i :=$ChoosePivot$(A, l, r)$// to be implemented
swap $A[l]$ and $A[i]$
$j :=$Partition$(A, l, r)$// also places the pivot correctly
Quicksort$(A, l, j-1)$
Quicksort$(A, j+1, r)$
Partition¶
Input: Array $A$ of $n$ distinct integers, left and right Endpoint $l,r \in \{1,\dots n\}$ with $l\leq r$. Pivot element is at position $l$.
Postcondition: elements of the subarray $A[l], A[l+1] \dots A[r]$ are partitioned around the pivot element.
Output: final position of the pivot-element
$p:=A[l]$
$i:= l+1$
for $j=l+1$ to $r$ do
if $A[j]<p$ then\\ if A[j]>=p do nothing
swap $A[j]$ and $A[i]$
$i:=i+1$
swap $A[l]$ and $A[i - 1]$\\ place the pivot correctly
return $i-1$
Laufzeit: linear in $r-l$
Laufzeitanalyse¶
Falls als Pivot der Median gewählt würde:
$$ T(n) = 2 \cdot T\left( \frac{n}{2}\right) + \Theta(n) $$
Die meiste Arbeit außerhalb der rekursiven Aufrufe wird dabei von
ChoosePivot (Komplexität für die Medianberechnung ist $O(n)$, siehe z.B. [Rou]) und Partition (Komplexität $\Theta(n)$) geleistet.
Für die Master-Methode ergeben sich so die Konstanten $a=b=2$ und $d=1$. Dies ergibt
$$ T(n) = \Theta(n\log n) $$
Zufällige Auswahl des Pivot-Elementes¶
Falls immer (z.B. durch Pech) das größte (oder kleine Element) ausgewählt würde, welche Laufzeitkomplexität hätte man dann?
- Gibt es dennoch eine einfachere Möglichkeit Quicksort zu implementieren als immer das Median-Element auszurechnen?
Die Medianberechnung ist vergleichsweise aufwändig.
Randomisiertes Quicksort¶
Wahl des Pivot-Elementes¶
In der Praxis wird meist ein zufälliges Element (gezogen aus einer Gleichverteilung) als Pivot-Element gewählt.
Theorem 5.1 (Laufzeit von randomized Quicksort)¶
Für jedes Eingabearray mit Länge $n\geq 1$ ist die durchschnittliche Laufzeitkomplexität $O(n \log n)$.
Durchschnitt bedeutet mathematisch Erwartungswert (expectation).
Intuition für Theorem 5.1
- bei Auswahl eines zufälligen Elementes erhält man zu 50% einen "approximierten Median" (größer als 25% und kleiner als 75% aller Werte)
- Dadurch wird der Rekursionsbaum (meist) nicht viel tiefer und ist einigermaßen ausgeglichen.
Bemerkung: Solche Hand-waving Argumente ersetzen keinen formalen Beweis. D.h. man kann nicht sicher sein, ob die Argumentation so wirklich richtig ist.
Für einen formalen Beweis siehe z.B. [Rou], Kapitel 5.5
mit zwei Vergleichen (ersten mit dem zweiten Element und das dritte mit dem vierten Element) kann man z.B. nicht folgende Fälle unterscheiden:
|1|2|3|4| <----> |1|3|2|4|¶
Beweis von Theorem 5.5¶
Erhält man bei $k$ Vergleichen auf zwei Arrays die gleichen Ergebnisse, kann man auf Grund dessen keinen Unterschied zwischen den beiden Arrays feststellen. Es gibt $2^k$ unterschiedliche Ergebnisse bei $k$ Vergleichen, d.h. man kann nur $2^k$ Möglichkeiten unterscheiden.
Für ein Array bestehend aus den Zahlen $\{1,2,\dots n\}$ gibt es $n!$ verschiedene Arrays (Permutationen).
Um also die verschiedenen Arrays aus den Zahlen $\{1,2,\dots n\}$ mit $k$-Vergleichen unterscheiden zu können, muss also gelten:
$$ 2^k \geq n! $$
Es gilt auch
$$ n! = n\cdot (n-1) \cdot (n-2) \dots 2 \cdot 1 \geq n\cdot (n-1) \cdot (n-2) \dots (n/2) \geq \left( \frac{n}{2}\right)^{n/2}$$
In Worten: Die erste Hälfte von $n\cdot (n-1) \cdot (n-2) \dots 2 \cdot 1 $ enthält $n/2$-Terme. Dabei ist jeder Term ist mindestens $n/2$ groß.
Also:
$$ 2^k \geq n! \geq \left( \frac{n}{2}\right)^{n/2} $$
Aus
$$ 2^k \geq \left( \frac{n}{2}\right)^{n/2} $$
ergibt sich mit Logarithmieren zur Basis 2 (d.h. $\log_2$) und der Eigenschaft, dass der Logarithmus eine streng-monotone Funktion ist:
$$ k \geq \frac{n}{2} \log_2 \left( \frac{n}{2}\right), $$ d.h. für die Anzahl der Vergleiche $k$ gibt es eine untere Grenze $\Omega\left( n \log n\right)$, d.h. man muss mindestens $\Omega (n \log n)$ Vergleiche (in einem Sortier-Algorithmus) durchführen.
QED
Literatur¶
- [Rou] T. Roughgarden, Algorithms Illuminated, Part 1: The Basics