prev up next

Previous: Mergesort Up: Sortieren Next: Bestimmung des Medians

Quicksort

Source: QuickSort.java     JavaDoc: QuickSort.html     Die Analyse der Laufzeit von Quicksort stützt sich auf folgende Rekursionsungleichung für die Anzahl der Schritte $f(n)$ bei $ n $ zu sortierenden Daten im günstigsten Fall (Partitionen sind immer gleich groß):


\begin{displaymath}
f(n)\leq \left\{ \begin{array}{ll}
c_{1} & \mbox{ f\uml {u...
...+ 2\cdot f (\frac {n}{2}) & \mbox{ sonst}
\end{array} \right.
\end{displaymath}

Daraus ergibt sich $f\in O(n \cdot \log n)$. Diese Komplexität gilt auch für den durchschnittlichen Fall; es lässt sich zeigen, dass die Zahl der Schritte nur um den konstanten Faktor 1.4 wächst.

Im ungünstigsten Fall (bei entarteten Partitionen) gilt $f \in O(n^{2})$.

Source: QuickSortTest.java     JavaDoc: QuickSortTest.html     Applet:


prev up next
Previous: Mergesort Up: Sortieren Next: Bestimmung des Medians