QuickSort (Pivotelement)

[Davision]

Erstmal guten Tag an alle,

ich sitze grad hier und pauke für meine anstehende Informatikklausur die den Schwerpunkt auf dynamische Datenstrukturen ... Bin jetzt grade am QuickSort angelangt und komme darüber ins Grübeln welche Methode am geeignetsten ist um das Pivotelement auszuwählen.
Ich steh jetzt natürlich vor der Qual der Wahl und wollte eure Meinung zu den verschiedenen Ansätzen hören.

1. Einfach das ganz linke bzw. rechte Element des Arrays nehmen.
2. Den Median der Elemente berechnen (natürlich nur wenn es sich um integer o.Ä. handelt) und den Wert auswählen der am nächsten dran ist.
3. Die ungefähre Mitte des Arrays nehmen (untere Grenze + obere Grenze) / 2

Welchen Ansatz haltet ihr für ideal oder habt ihr einen noch ganz anderen Ansatz?

 

[hauptDev]

Ich würde dir zu 3. raten oder du ermittelst das Pivotelement einfach jedes Mal zufällig.

 

[stg]

Kommt immer drauf an....

Wie groß sind die Listen? Wie gut sind die Listen "vorsortiert"? Wie teuer ist ein einzelner Vergleich? undundund...

Eine perfekte Lösung gibt es nicht. Worst Case ist und bleibt immer in O(n^2) beim QuickSort.

Dein erster und dritter Ansatz unterscheiden sich nicht wirklich. Ist dir klar wieso?

Deinen zweiten Ansatz kannst du getrost streichen, denn der führt zwangsläufig zu einer katastrophalen Laufzeit (insbesondere dann, wenn Vergleiche zusätzlich noch teuer sind), auch wenn das gewählte Pivot-Element auf diese Art natürlich optimal wäre. Eine leichte Abwandlung, der "median of three", führt aber oftmals zu ebenfalls recht guten Pivot-Elementen. Hier bestimmst du zufällig drei Indize und ermittelst den Median von diesen dreien. Das verrigert die Chance ein "schlechtes" Pivot-Element zu erwischen, deutlich.