Würde die Verwendung des Mittelwerts als Drehpunkt die Quicksortierung beschleunigen?

7

Irgendwie habe ich letzte Nacht über Quicksort nachgedacht und auf Wikipedia darüber gelesen. Das Interessante für mich war: „Wenn wir konsequent einen Pivot aus den mittleren 50 Prozent wählen könnten, müssten wir die Liste höchstens aufteilenlog4/3n. Die Wahl des Drehpunkts scheint ein mögliches Problem der Quicksortierung zu sein, das dazu führen kannO(n2) Verhalten.

Meine Idee war: Wenn man in jedem Schritt den Mittelwert der Partition als Drehpunkt verwenden würde , könnte dies die Geschwindigkeit erheblich erhöhen. Insbesondere nach einigen Schritten, wenn sich Ausreißer in ihrer eigenen Aufteilung der Liste befinden, sollten Mittelwert und Median sehr nahe beieinander liegen (erneut bei großen Listen). Die zusätzliche Zeit während jedes Schritts zur Berechnung des Mittelwerts sollte betragenn. Deshalb:

Quicksort geschätzte Zeit: nAlog4/3n

Quicksort_mean geschätzte Zeit: 2nAlog5/3n

(5/3 ist höchstwahrscheinlich eine konservative Schätzung von mir, könnte genauso gut näher an 2 liegen, da Teilmengen schnell ohne Ausreißer sein sollten). Ab etwa 10.000 Einträgen wäre Quicksort_mean also (im Durchschnitt) schneller als Quicksort. Darüber hinaus würde es niemals riskieren zu seinO(n2), da es verpflichtet ist, nicht das minimale oder maximale Element des Stapels zu nehmen.

Meine Hauptfrage ist: Habe ich etwas verpasst? Ich muss zugeben, ich habe Quicksort selbst nie implementiert, sodass ich möglicherweise andere Teile des Ganzen (Speicher usw.) verpasse.

Johannes Becker
quelle
1
Haben Sie die aktualisierte Wiederholung tatsächlich gelöst, um diese "Laufzeit" zu erhalten, oder haben Sie einfach eine weitere hinzugefügt? n? (Letzteres wäre falsch.)
Raphael
(Haftungsausschluss: Es ist lange her, dass ich mich ernsthaft mit diesem Zeug befasst habe, und mein Wissen ist möglicherweise veraltet.) Schnelle Sortierung ist nur um den Faktor zwei schneller als die Hauptkonkurrenten, die ein gutes Worst-Case-Verhalten haben Wenn Sie die schnelle Sortierung im besten Fall erheblich verlangsamen, wird der Grund für die Verwendung anstelle anderer Algorithmen beseitigt.
Ich habe einfach ein weiteres n hinzugefügt. Ich weiß, dass es 'falsch' ist, aber die Berechnung des Mittelwerts sollte superschnell sein (n Additionen, die beim Sortieren und der Anzahl der Partitionsunterteilungen durchgeführt werden könnten). Mein Wissen über Konkurrenten ist nicht sehr gut (wie gesagt, war nur ein völlig zufälliger Gedanke im Halbschlaf ...)
Johannes Becker

Antworten:

10

Die Verwendung des Mittelwerts für Ihre Partition verhindert das nicht Ω(n2)Worst-Case-Verhalten. Es tritt auf, wenn die Eingabeliste exponentiell zunimmt. Betrachten Sie die Eingabe:

1,n2,n3,,nn

Der Mittelwert dieser Menge ist (asymptotisch) nn1So erhalten Sie die schlechteste Partition, die möglich ist. Dies ist ein kleiner Betrug, wenn man bedenkt, dass das Speichern der Liste dauertΩ(n2)Leerzeichen, wenn die Zahlen als Ganzzahlen dargestellt werden. Wenn Sie jedoch Gleitkommazahlen sortieren, ist dieses Szenario denkbar.

Es ist jedoch möglich, den Median einer Menge (oder einer anderen Ordnungsstatistik für diese Angelegenheit) in zu berechnenO(n) Wenn Sie sich also wirklich für Laufzeitgarantien für eine schnelle Sortierung interessieren, sollten Sie diese anstelle des Mittelwerts verwenden.

In allen praktischen Szenarien sind die zusätzlichen Kosten für die Berechnung des Mittelwerts / Medians jedoch so hoch, dass die Auswahl eines zufälligen Pivots fast immer schneller ist.

Tom van der Zanden
quelle
Das ist eine mittlere Liste: D (Ich denke, Sie würden ziemlich schnell die Unendlichkeit erreichen, sodass Sie keine sehr hohe Zahl n haben könnten). Mein Punkt war, dass O (n) nicht automatisch O (n) ist. Im Vergleich dazu ist die Berechnung des Medians A * n mit A größer als 1. Im Vergleich dazu sollte die Berechnung des Mittelwerts nahe bei 1 * n liegen. Ich denke also, es könnte den Laufzeitdurchschnitt erhöhen (war nicht so interessiert an Laufzeitgarantien). Ich muss zugeben, das Ganze war nur ein Gedankengang, der mich heute Nacht nicht alleine gelassen hat. Also habe ich beschlossen, es hier zu platzieren, falls jemand es interessant findet ...
Johannes Becker
1
Der letzte Absatz ist sehr wichtig: Ja, Sie können die Rekursionstiefe optimieren, indem Sie bessere Drehpunkte auswählen. Dies ist jedoch mit Kosten verbunden. Eine strenge Analyse ist erforderlich, um festzustellen, ob es sich lohnt. Siehe zB Sedgewicks These; Die Antwort war oft "Nein" (Intuition: Sie zahlen immer für die Wahl besserer Drehpunkte, aber nur manchmal für die naivere Wahl).
Raphael
Viele Sortierkriterien haben keinen "Mittelwert", z. B. das Sortieren einer Liste von Personen nach Nachnamen.
Gnasher729