Was ist der Vorteil von randomisierten Quicksort?

Question

In ihrem Buch Randomisierte Algorithmen, Motwani und Raghavan eröffnen die Einführung mit einer Beschreibung ihrer Randqs -Funktion - randomisierte Quicksort -, wobei der Drehzahl, der zur Partitionation des Sets in zwei Teile verwendet wird, zufällig ausgewählt wird.

Ich habe seit einiger Zeit mein (zugegebenermaßen etwas untermachtes) Gehirn über diesen Gehirnen gekürzt, aber ich konnte nicht sehen, welchen Vorteil dieser Algorithmus jedes Mal einfach das mittlere Element (im Index, nicht die Größe) hat.

Ich nehme an, was ich nicht sehen kann, ist Folgendes: Wenn sich der Anfangssatz in einer zufälligen Reihenfolge befindet, was ist der Unterschied zwischen der Auswahl eines Elements an einem zufälligen Ort im Satz und der Auswahl eines Elements an einer festen Position?

Kann mich jemand in ziemlich einfachen Worten aufklären?

Answer 1

Wenn das Eingangsarray zufällig einheitlich verteilt ist (wie Sie festgestellt haben) gibt es keinen Unterschied zwischen immer ein Element an einer festen Position (z. B. die mittlere, wie Sie vorschlagen) oder ein zufällig ausgewähltes Element auszuwählen.

Ihre Verwirrung scheint also aus der Tatsache zu kommen, dass Sie annehmen, dass ein Sortieralgorithmus (in der Praxis) erwarten kann, dass das Eingabearray immer zufällig verteilt wird.

Answer 2

Wie von Jernej festgestellt, ist die Annahme, dass alle Permutationen des Eingangs gleich wahrscheinlich in der Realität gilt. Die erste Idee könnte darin bestehen, das Eingangsarray durchzuführen. Dies würde funktionieren, aber es ist einfacher, die Situation zu analysieren, in der ein Drehpunkt zufällig ausgewählt wird. Dies ist auch als bekannt als Stichproben.