Eine Frage zum Quicksort

[Katzenstreik]

Hallo miteinander,

ich beschäftige mich gerade mit dem Quicksort und stelle mir folgende Frage:

Ich zerteile eine Folge von Elementen ja in zwei Teile, indem ich das mittlere Element (also n/2) dafür nehme. Es ist doch durchaus möglich das das n/2te Element das kleinste oder meinetwegen fast das kleinste Element ist, wenn ich z.b. von dieser Folge ausgehe: Folge= {3,7,2,4,1,10,6,3,9}

Hierbei müsste ich dann doch alle Elemente in die zweite, also rechte hälfte transportieren.

So macht der Quicksort doch keinen Sinn mehr oder wenn das mittlere nur fast das kleineste ist, nur wenig Sinn. Warum wird in Büchern genau diese Vorgehensweise beschrieben? Gibt es keine bessere oder versteh ich was falsch?

Danke für eure Antworten.

 

[Final_Striker]

Wieso macht QS da keinen Sinn? Die rechte Hälfte wird dann sortiert.

 

[Katzenstreik]

naja, die Zeitkomplexität beträgt dann n^2 und ist somit nicht besser als einfache andere Sortierverfahren.

Worum es mir geht ist, ob es nicht mehr Sinn macht die Folge anders zu teilen, als mit n/2.

 

[Final_Striker]

QS hat halt in Worst-Case eine Komplexität von n^2, da kannst du auch nichts daran ändern. Da haben sicher schon genug schlaue Köpfe sich Gedanken darum gemacht. ;-)

 

[nununana]

Eine Verbesserung liegt in der Wahl des Pivotelements. z.B. bildet man aus 3 Elementen den Median. Oder man wählt das Pivotelement zufällig. Das Mittlere wird oft gewählt, weil es dann mit bereits sortierten Folgen keine Probleme gibt. Gibt es viele gleiche Elemente, ist es besser, ein anderes Verfahren zu wählen.

 

[Ezra]

Das gibt es. Man kann den Median bestimmen: Median-Algorithmus
Dann wird die Laufzeitkomplexität auf O(n) reduziert.

Allerdings ist der konstante Faktor so groß, dass sich ein derartiges Verfahren nur bei wirklich großen n lohnt.

Edit:

z.B. bildet man aus 3 Elementen den Median. Oder man wählt das Pivotelement zufällig.

Das verbessert die Laufzeitkomplexitätsklasse für den worst case aber nicht.
Auch für ein zufällig gewähltes Pivot besteht die Möglichkeit, eine worst-case-Folge zu treffen.
Beim Median aus drei Elementen reduzierst Du höchstens den konstanten Faktor.

 

[nununana]

Die Wahrscheinlichkeit ist dann aber extrem gering.

 

[Ezra]

Warum sollte sie geringer sein als bei n/2?

 

[Katzenstreik]

den median zu bilden find ich gut. Auch gut finde ich dass du gleich darauf hinweist, dass dies bei(fast)sortierten Folgen nachteilig zu bewerten ist.

Also kann man sagen, dass wenn man seine Folge nicht kennt die Wahl des Pivotelements ein Glücksspiel darstellt

(Obwohl ich persönlich einen Median immer bevorzugen werde...)

Danke Leute!

 

[nununana]

Warum sollte sie geringer sein als bei n/2?

Warum sollten die Wahrscheinlichkeiten bei sortierten Folgen gleich sein? Wie hoch sind Wahrscheinlichkeiten für sortierte Folgen? Kannst auch fragen.

 

[Ezra]

Entweder verstehe ich Dich falsch oder Du mich.
Wo geht es denn um sortierte Folgen? Bei Quicksort mit n/2 als Pivot ist es nicht die sortierte Folge, die den worst case liefert. Das beste Beispiel dafür steht im Ausgangspost des TE.
Wenn Du nun behauptest, ein zufälliges Pivot sei besser als n/2 als Pivot, kann ich Dir nicht zustimmen. Die Wahrscheinlichkeiten, in den jeweiligen Fällen genau den worst case zu erwischen, sind gleich.

Auch gut finde ich dass du gleich darauf hinweist, dass dies bei(fast)sortierten Folgen nachteilig zu bewerten ist.

Das habe ich nicht gesagt. Ich sprach von kleinen Folgen (kleines n).

 

[nununana]

jaaa, missverständnisse. wird als pivot immer das erste/letzte element der teilfolge zurückgegeben, ist das schlecht. das kann passieren, wenn erstes oder letztes als pivot gewählt wird UND die folge bereits sortiert is.
um das zu vermeiden, nimmt man die mitte. man kann auch zufälliges element wählen. natürlich gibt es keinen unterschied in der wahrscheinlichkeit (mind. 2/n mal 2/(n-1) usw.), die der worst case hat. aber man kann davon ausgehen, dass öfters als sonst die sortierte folge sortiert werden soll.
TE hat ja auch gefragt, wie man pivot alles wählen kann. da hab ich mich hauptsächlich auf wiki gestützt, wo das auch erwähnung findet (n/2, zufällig, 3 elemente, alle usw.). vor-/nachteile muss man dann eben versuchen zu erklären oder in der praxis herausfinden.