Quicksort Pivotelement?
Der Quicksort wählt ja als erstes ein Pivotelement aus. Wie wählt er das Pivotelement aus? Ist das zufällig oder hat das irgendeinen Sinn?
Danke schonmal.
3 Antworten
Das kann zufällig sein. Kann aber auch mittels weiterer Verfahren so gewählt wird, dass es ungefähr in der Mitte der Werte liegt. Das macht den Algorithmus im Worst-Case erheblich besser, ist aber auch selbst aufwändig.
Naiverweise nimmt man z.B. einfach immer das letzte Element.
Idealerweise soll das Pivot so getrennt werden, daß die Partitionen gleich groß werden. der Median ist in der Bestimmung allerdings teuer.
Wähle ich das Pivot zufällig, trenne ich zwar meist asymmetrisch, allerdings tritt eine ungünstige Trennung (alle Elemente in einer Partition) mit extrem kleiner Wahrscheinlichkeit ein, erst recht wiederholt. Insbesondere aber, kann ich keine Eingabe konstruieren, die immer für eine ungünstige Partitionierung sorgt - während die Randomisierung ansich billig ist.
Andere Möglichkeiten wären beispielsweise eien Stichprobenmedianbestimmung o.ä. .
Idealerweise sollte der Median ausgewählt werden.
Da diese Suche aber aufwendig ist, wird meist ein zufälligs Element herangezogen.