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ß):

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

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: