Quicksort

Wie bei vielen anderen Sortierverfahren (Bubblesort, Mergesort, usw.) ist auch bei Quicksort die Aufgabe, die Elemente eines Array a[1..n] zu sortieren. Quicksort ist zudem ein Divide-and-Conquer-Verfahren.

Devide: Wähle ein Pivot-Element p (z.B. das letzte) und partitioniere a[l..r] gemäß p in zwei Teile a[l..i-1] und a[i+1] (durch geeignetes Vertauschen der Elemente), wobei anschließend a[i]=p.

Conquer: Sortiere a[l..i-1] und a[i+1..r] rekursiv.

Algorithmus:

proc qs(a,l,r)
{
		 if $l\geq r$ then return fi
		  $\char93$ifdef Variante 2
		 		 vertausche a[random(l,r)] mit a[r]  ;
		 $\char93$endif
		 p:=a[r] ;
		 i:=l; j:=r ;
		 repeat
		 		 while i<j and $a[i]\leq p$ do i++ od
		 		 while i<j and $p\leq a[j]$ do j- od
		 		 if i<j then vertausche a[i] und a[j];
		 until i==j;
		 vertausche a[i] und a[r];
		 qs(a,l,i-1);
		 qs(a,i+1,r);
} 

Bemerkung: Der oben formulierte Algorithmus benötigt pro Durchlauf in der Regel n+1 Schlüsselvergleiche. Lediglich wenn die beiden Indizes zusammenfallen (was nur bei einem Pivotduplikat passieren kann), benötigt er nur n Vergleiche. Durch geschicktes Einstreuen von if-Abfragen kann man auch in jedem Fall mit n-1 Schlüsselvergleichen auskommen.

Komplexität von Quicksort:

• Best-case-Analyse: Quicksort läuft natürlich am schnellsten, falls die Partitionierung möglichst ausgewogen gelingt, im Idealfall also immer zwei gleichgroße Teilintervalle entstehen, das Pivot ist dann stets der Median.
  
  
  
• Worst-case-Analyse: Z.B. bei eine aufsteigend sortierte Eingabe.
  
  
  
• Average-case: Da die Laufzeit von Quicksort sehr stark von den Eingabedaten abhängt und sich demnach keine scharfe allgemeingültige Schranke angeben läßt, kann man die Frage stellen, wie lange der Algorithmus ``im Mittel`` zum sortieren von n Elementen braucht. Um jedoch überhaupt eine derartige Analyse durchführen zu können, muß man zuerst die genaue Bedeutung von ``im Mittel`` festlegen. Eine naheliegende Annahme ist, daß alle möglichen Permutationen der Eingabedaten mit gleicher Wahrscheinlichkeit auftreten.
  
  

  Beweis: (Variante mit n-1 Vergleiche pro Durchlauf)
  Sei C_n die Anzahl der Vergleichen bei dem Feld der Länge n. C₀=C₁=0.

  $$C_n=n-1+\frac{1}{n} \sum_{j=1}^{n}(C_{j-1}+C_{n-j})$$

  Da

  i)

  für festes $j\in\{1,\cdots,n\}$ das Produkt (in beiden Varianten) das j-kleinstes Element ist und

  ii)

  auch für die rekursiven Aufrufe wieder alle Eingabepermutationen gleichwahrscheinlich sind:

  $$\begin{split} \Rightarrow \hspace{2cm} C_n & = n-1+\frac{2}{... ... 2 \left[\text{H}_{n+1} -2 +\frac{1}{(n+1)} \right] \end{split}$$

  $\Rightarrow C_n=2(n+1)\left(\text{H}_{n+1}-2+\frac{1}{n+1}\right)$ ; H$_n\approx \ln{n}+0.57721\cdots+o(1) \\ \Rightarrow C_n\approx 2n\ln{n}-4n+o(n) \approx 1.386 n \log{n}$ $\Diamond$