Quicksort mit Median of Three

[alzaimar]

Hmm, müsste man mal bei Wiki eventuell verbessern. Grundsätzlich ist das randomisierte Quicksort rein rechnerisch Optimal, da der Worstcase keine 'normale' Folge von Zahlen ist, sonden eben zufällig, also in der Praxis nicht zu erwarten.

In der Praxis ist der Overhead der Random-Funkion jedoch zu hoch, um die theoretisch möglichen Performancevorteile in bare Münze zu verwandeln. Das Median Of Three Verfahren nimmt nur den Mittelwert des linken, mittleren und Rechten Elements (Würde man diese zufällig wählen, wäre der Worstcase genauso warscheinlich, wie die des einfachen randomized Quicksort). Die relativ einfache Optimierung verbessert das Laufzeitverhalten um 3-10%.

Mit dem Median Of Three-Verfahren wird der Worstcase (sortierte Listen) vermieden.