Quicksort mit Median of Three

[3_of_8]

Morgen.

Also bei einer Übungsaufgabe der Uni Passau (Kurs Programmieren 1) heißt es:

"Implementieren sie QuickSort bei Arrays. Verwenden sie dazu das Median of Three Pivot."

Was genau kann ich mir darunter vorstellen? Eine Beschreibung würde ich mir wünschen, da ich diese Aufgabe vor allem mache, um herauszufinden, ob ich schon für Programmieren II geeignet bin, und daher die Vorlesung, in der das erörtert wurde, nicht besucht habe.

Ein eventueller Pseudocode wäre auch nicht schlecht, aber nicht unbedingt nötig.

[DGL-luke]

http://de.wikipedia.org/wiki/Quicksort

da steht bei Laufzeit:

Zitat:

Ein Ansatz, um worst-case-Laufzeiten zu verhindern, ist, als Pivotelement ein zufällig bestimmtes Element zu wählen. Bei diesem randomisierten Quicksort ist die Wahrscheinlichkeit, dass das Pivotelement in jedem Teilungsschritt so gewählt wird, dass sich die worst case-Laufzeit ergibt, extrem gering, so dass man praktisch von einer Komplexität von O(n·log(n)) ausgehen kann. Eine andere Möglichkeit ist die Verwendung des Medians von z.B. drei zufällig gewählten Elementen. Durch geschickte Wahl des Pivotelementes kann man aber nur das mittlere schlechteste Verhalten verbessern. Vollständig verhindern kann man das Eintreten des Worst Cases jedoch nicht.

Über google solltest du vom prinzip bis zu vollständigen Implementierungen alles finden

[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.