Ich lerne etwas über Quicksort und möchte verschiedene Arrays veranschaulichen, auf denen Quicksort Schwierigkeiten haben würde. Die Quicksortierung, an die ich denke, hat kein anfängliches zufälliges Mischen, führt 2 Partitionen durch und berechnet den Median nicht.
Bisher habe ich mir drei Beispiele ausgedacht:
[1,2,3,4,5,6,7,8,9,10] - when the array is sorted
[10,9,8,7,6,5,4,3,2,1] - when the array is reversed
[1,1,1,1,1,1,1,1,1,1] - when the array is the same values
[1,1,1,2,2,2,3,3,3,3] - when there are few and unique keys
Zum Beispiel bin ich mir da nicht sicher:
[1,3,5,7,9,10,8,6,4,2]
Was macht ein Array aus, mit dem Quicksort Schwierigkeiten hat, im Vergleich zu einem Array, bei dem es (fast) ideal ist?
algorithms
sorting
mrQWERTY
quelle
quelle
[2,1,2,1,2,1,2,1]und das ist das Ganze Antworten). Das Ziel der Frage wäre im Idealfall eines, bei dem andere Menschen mehr über das Warum (das eine Antwort hat) als über Beispiele (für die es unzählige gibt) herausfinden können .Antworten:
Jeder Sortieralgorithmus hat einen Worst-Case, und in vielen Fällen ist der Worst-Case wirklich schlecht, daher lohnt es sich, ihn zu testen. Das Problem ist, dass es keinen einzigen schlimmsten Fall gibt, nur weil Sie den grundlegenden Algorithmus kennen.
Häufige Worst-Cases sind: bereits sortiert; umgekehrt sortiert; fast sortiert, eines außer Betrieb Element; alle Werte gleich; Trotzdem ist der erste (oder letzte) höher (oder niedriger). Wir hatten einmal eine Sorte, bei der der schlimmste Fall ein bestimmtes Sägezahnmuster war, das sehr schwer vorherzusagen war, aber in der Praxis durchaus üblich war.
Der schlimmste Fall für Quicksort ist einer, bei dem immer der schlechteste Drehpunkt ausgewählt wird, sodass eine der Partitionen nur ein einziges Element enthält. Wenn der Pivot das erste Element ist (schlechte Wahl), sind bereits sortierte oder invers sortierte Daten der schlechteste Fall. Bei einem Median von drei Pivot-Daten, die alle gleich sind oder nur die ersten oder letzten unterschiedlich sind, reicht der Trick aus.
Für Quicksort ist die durchschnittliche Komplexität nlogn und der schlechteste Fall ist n ^ 2. Der Grund, warum es sich lohnt, das Worst-Case-Verhalten auszulösen, liegt darin, dass dies auch die größte Rekursionstiefe erzeugt. Für eine naive Implementierung könnte die Rekursionstiefe n sein, was einen Stapelüberlauf auslösen kann. Das Testen anderer extremer Situationen (einschließlich des besten Falls) kann sich aus ähnlichen Gründen lohnen.
quelle
O(NlogN)Leistung oder besser) der schlechteste und der durchschnittliche Fall die gleiche Komplexität haben. Dies deutet darauf hin, dass es sich normalerweise NICHT lohnt, auf die schlimmsten Fälle zu testen. (Angesichts der Tatsache, dass der Test wahrscheinlichO(N)... oder schlimmer ist.)Ein Algorithmus entgeht den meisten schlechten Fällen mithilfe eines zufälligen Pivots, wobei kontinuierliche Elemente ausgeschlossen werden, die einem Pivot aus der Partitionierung und der asymmetrischen Suche entsprechen. Es sucht vorwärts ein Element, das größer oder gleich einem Drehpunkt ist, und sucht rückwärts ein Element, das kleiner als ein Drehpunkt ist.
Ich danke MichaelT, Asymmetrische Suche wurde entwickelt, um [2,1,2,1,2,1,2,1] aufzulösen.
Das folgende Ergebnis wird von meiner Funktion qsort_random () generiert. N = 100.000
Die meisten Fälle sind schneller als ein zufälliges Muster. Das Talmuster ist ein schlechter Fall für die meisten Pivot-Auswahlen.
qsort_log2 () entgeht einem fehlerhaften Fall, indem ein Pivot in log2 (N) -Elementen ausgewählt wird.
qsort (3) verwendet die GNU-Bibliothek, bei der es sich um eine Zusammenführungssortierung der Indexsortierung handelt.
qsort_trad () wählt einen Pivot im ersten, mittleren und letzten Element aus.
qsort_random () und qsort_log2 () verwenden kein Tauschen.
Quell-C-Programme und -Skripte werden in github veröffentlicht .
quelle