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

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 aufteilen$\log_{4/3} n$. Die Wahl des Drehpunkts scheint ein mögliches Problem der Quicksortierung zu sein, das dazu führen kann$O(n^2)$ 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 betragen$n$. Deshalb:

Quicksort geschätzte Zeit: $nA\log_{4/3} n$

Quicksort_mean geschätzte Zeit: $2nA\log_{5/3} n$

(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 sein$O(n^2)$, 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.

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

$1,n^2,n^3,\ldots,n^n$

Der Mittelwert dieser Menge ist (asymptotisch) $n^{n-1}$So erhalten Sie die schlechteste Partition, die möglich ist. Dies ist ein kleiner Betrug, wenn man bedenkt, dass das Speichern der Liste dauert$\Omega(n^2)$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 berechnen$O(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.