Welches Maß für die Störung bei der Analyse von Quicksort zu verwenden ist

9

Ich versuche zu verstehen, warum Quicksort mit Lomuto-Partition und festem Pivot bei zufällig generierten Eingaben unregelmäßig, aber insgesamt schlecht funktioniert. Ich denke, obwohl die Eingaben zufällig generiert werden, können die Sequenzen sehr ordentlich sein, aber ich bin mir nicht sicher, wie ich den Grad der Störung in den Sequenzen messen soll. Ich habe darüber nachgedacht, die Anzahl der Inversionen zu verwenden, aber ich habe anhand dieser anderen Frage gesehen , dass dies in diesem Fall keine wirklich gute Maßnahme ist.

Der Grund, warum ich vermute, dass meine zufälligen Sequenzen viel "Ordnung" haben, ist, dass das Randomisieren des Pivots das Leistungsproblem behebt. Theoretisch sollte es jedoch keine Leistungsprobleme bei diesen angeblich "zufälligen" Eingabesequenzen geben.

algorithms sorting Robert S. Barnes
quelle
Ein gutes Maß für die Unordnung bei solchen Dingen ist die Komplexität von Kolmogorov. Grundsätzlich heißt es, dass die am meisten ungeordneten Zeichenfolgen inkompressibel sind. Dies führt zur Inkompressibilitätsmethode, mit der beispielsweise die Durchschnittsanalyse von Sortieralgorithmen durchgeführt und die Beziehung zwischen Durchschnitts- und Worst-Case-Analyse ermittelt wurde.
Peter
Ich sollte beachten, dass ich ein Student bin ... Ich suchte nach etwas Unkomplizierterem
Robert S. Barnes
Verwandte Frage .
Raphael
Sie sollten eher einen Programmierfehler als einen schwenkbaren Fall des Gegners vermuten. Sortieren Sie einfach eine verschlüsselte Folge von ganzen Zahlen von 1 bis N, um zu sehen, ob Ihr Algorithmus sortiert!
Yves Daoust
@YvesDaoust Ich denke nicht, dass das wirklich wichtig ist. Die Menge an "Nicht-Monotonie" ist wirklich nur die Kolmogorov-Komplexität der Zeichenfolge der Längedas codiert die Reihenfolge der Elemente in der Sequenz. Natürlich ist es nicht berechenbar, und Sie müssen über tiefe Zeichenketten wie pseudozufällige nachdenken, aber es ist nützlich in dem Sinne, dass jedes Maß der Störung im Wesentlichen eine Annäherung an die Kolmogorov-Komplexität ist. Und Sie müssen es nicht berechnen, um die Dinge damit zu beweisen. Mit der Inkompressibilitätsmethode wurden viele Komplexitätsergebnisse gezeigt. logn!
Peter

Antworten:

1

Lomuto vs Hoare Die
Lomuto-Partition leidet beim Sortieren gleicher Schlüssel, die Hoare-Partition dagegen nicht.
Beide Partitionsschemata leiden gleichermaßen, wenn ein vom Median entfernter Drehpunkt verwendet wird.

Maß für die Störung
Das Maß für die Störung, das für die Zwecke der Quicksortierung ausgewählt werden soll, ist einfach.
A: Wie weit vom Median entfernt ist der feste Drehpunkt im Vergleich zu zufälligen Daten?
Wenn Sie auf der Verwendung der Lomuto-Partition bestehen und davon ausgehen, dass doppelte Werte zulässig sind, müssen Sie den folgenden Test gegen Zufälligkeit hinzufügen:
B: Wie viele doppelte Elemente gibt es im Vergleich zu zufälligen.

Natürlich ist es ziemlich dumm anzunehmen, dass doppelte Werte in Ihrem Datensatz zulässig sind und dennoch die Lomuto-Partition auswerten. Daher sollten Sie wahrscheinlich entweder vorher Duplikate entfernen oder zur Hoare-Partition wechseln oder davon ausgehen, dass Duplikate selten sind.

Beide Maßnahmen sind trivial zu quantifizieren.

Wir können pathologische Daten ausschließen.
Andere Abweichungen von der Zufälligkeit spielen für die Analyse von Quicksort keine Rolle. Solange sich der Pivot in der Nähe des Medians befindet, funktioniert er bei allen Daten, die nicht pathologisch sind, gut.
Der Abstand zum Zufall müsste in der Tat groß sein, um schnell-pathologisch zu sein, also können wir das ausschließen.

Verwenden Sie niemals feste Pivots in echtem Code.
Beachten Sie, dass Sie sich einem Denial-of-Service-Angriff öffnen , wenn Sie echten Code mit einem festen Pivot *) schreiben (was auch immer dieser Pivot sein mag), da ein Angreifer einen einfügen kann pathologischer Wert genau an diesem Punkt und daher sollten Sie immer ein zufälliges Element als Drehpunkt wählen.

*) oder mehrere Pivots, wenn Sie das Beste aus x Pivots auswählen.

Johan - Monica wieder einsetzen
quelle