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)$
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$
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) $$Falls immer (z.B. durch Pech) das größte (oder kleine Element) ausgewählt würde, welche Laufzeitkomplexität hätte man dann?
Die Medianberechnung ist vergleichsweise aufwändig.
In der Praxis wird meist ein zufälliges Element (gleichverteilt) als Pivot-Element ausgewählt.
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
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:
Erhält man bei $k$ Vergleichen auf zwei Arrays die gleichen Ergebnisse, kann man auf Grund dessen keinen Unterschied zwischen den beiden Arrays feststellen. Da es $2^k$ unterschiedliche Ergebnisse bei den Vergleichen gibt, kann man nur soviele Möglichkeiten unterscheiden.
Für ein Array bestehend aus den Zahlen $\{1,2,\dots n\}$ gibt es $n!$ verschiedene Arrays.
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} $$Somit
$$ 2^k \geq \left( \frac{n}{2}\right)^{n/2} $$Logarithmieren mit $\log_2$ (streng-monotone Funktion)
$$ k \geq \frac{n}{2} \log_2 \left( \frac{n}{2}\right) = \Omega\left( n \log n\right) $$QED
Erinnerung: $\Omega$ symbolisiert eine untere Grenze.