Schnelle Sortierung Worst Case

Question

Ich arbeite an dem Programm, das im Folgenden nur benötigt wird, um es besser zu verstehen.

Was ist die Worst-Case-Laufzeit für Quicksort und was kann zu dieser schlechteren Leistung führen? Wie können wir Quicksort-Programm ändern, um dieses Problem zu verringern?

Ich weiß, dass es Worst Case O(n^2) hat, und ich weiß, dass es auftritt, wenn das Pivot eindeutige minimale oder maximale Element. Meine Frage ist, wie kann ich das Programm ändern, um dieses Problem zu mildern.

Ein guter Algorithmus wird gut sein.

Answer 1

Es ist eine Weile her, aber ich denke, der schlimmste Fall für Quicksort war, wenn die Daten bereits sortiert waren. Eine schnelle Überprüfung, ob die Daten bereits sortiert sind, könnte dieses Problem beheben.

Answer 2

Eine einfache Änderung ist die zufällige Wahl des Pivot. Dies ergibt gute Ergebnisse with high probability.

Answer 3

Die Quicksort-Leistung hängt von Ihrem Pivot-Auswahlalgorithmus ab. Der naivste Pivot-Auswahlalgorithmus besteht darin, einfach das erste Element als Pivot zu wählen. Es ist leicht zu sehen, dass dies zu einem Worst-Case-Verhalten führt, wenn Ihre Daten bereits sortiert sind (das erste Element ist immer das Minimum).

Es gibt zwei gängige Algorithmen, um dieses Problem zu lösen: Nach dem Zufallsprinzip einen Drehpunkt wählen oder den Median von drei wählen. Zufall ist offensichtlich, also werde ich nicht ins Detail gehen. Das Median von drei beinhaltet die Auswahl von drei Elementen (normalerweise das erste, mittlere und letzte) und die Auswahl des Medians als Drehpunkt.

Da Zufallszahlengeneratoren typischerweise pseudozufällig (also deterministisch) sind und ein nicht zufälliger Median von drei Algorithmen deterministisch ist, ist es möglich, Daten zu konstruieren, die zu Worst-Case-Verhalten führen, aber selten kommt es dazu normale Nutzung.

Sie müssen auch die Auswirkungen auf die Leistung berücksichtigen. Die Laufzeit Ihres Zufallsgenerators beeinflusst die Laufzeit Ihres Quicksort. Mit einem Median von drei erhöhen Sie die Anzahl der Vergleiche.

Answer 4

Schlechtesten Zustand:

Wenn jedes Mal Pivot ist gewählt 'größte' oder 'kleinste' und dieses Muster wiederholt

für So 1 3 5 4 2

Wenn schwenkt in der Reihenfolge 1,2,3,4,5 oder 5,4,3,2,1

gewählt werden, dann ist die schlechteste Laufzeit O (n * n)

Wie im schlimmsten Fall vermeiden:

(1) Teilen Sie das Array in fünf sets.So wenn 1..100 die Sätze sind (1..20) (21..40) (41..60) (61..80) (81 ..100)

(2) Wähle Median von fünf ersten Elementen in jedem der so eingestellt, (3) (23) (43) (63) (83)

(3) nun den Median wählen unter sie als der Drehpunkt so hier seine (43)

Answer 5

Die Worst-Case-Laufzeit hängt von der Partition-Methode in Quick-Sort. Das hat zwei Aspekte:

• die Pivot-Auswahl
• wie um den Dreh

Gute Strategien partitionieren die Pivot auszuwählen, die in früheren Veröffentlichungen (Median der Mediane oder Median von drei outlinied worden oder Randomisierung). Aber selbst wenn der Pivot weise ausgewählt wird, im Extremfall, wenn ein Array alle gleichen Elemente aufweist, führt dies zu einer Worst-Case-Laufzeit, wenn nur zwei Partitionen erstellt werden, weil man die gleichen Elemente trägt, also alle Elemente:

• dies bewirkt, dass partion genannt wird n-mal, jeder davon unter n/2 in Durchschnitt, was zu O (n²)
• das ist nicht gut, weil es kein theoretisches Worst-Case-Szenario ist aber ein ganz allgemeines
• Beachten Sie, dass dies nicht durch das Auffinden der leeren Partition gelöst wird, da der Pivot den höchsten oder niedrigsten Elementwert haben könnte (zB Median ist 5, was auch der höchste Elementwert ist, aber es könnte immer noch ein paar fehlplatziertegeben5 Werte)

Ein Weg, um dieses Problem in drei Partitionen partitioniert ist, ein unterer (Elemente < Schwenk), ein gleiches (Elemente = Schwenk) und eine obere Trennwand. Die "= Pivot-Elemente" befinden sich in ihrer endgültigen Position. Die untere und obere Partition muss noch sortiert werden, wenn sie nicht leer ist.

Zusammen mit Randomisierung, Median der Mediane oder einer Kombination, um einen Drehpunkt auszuwählen, ist ein Worst-Case-Szenario ziemlich selten, aber nicht unmöglich, was den Algorithmus mit einer Worst-Case-Obergrenze von O (n²) belässt.