Was ist der Vorteil von Randomized Quicksort?

18

In ihrem Buch Randomized Algorithms , Motwani Raghavan und öffnet die Einführung mit einer Beschreibung ihrer Funktion RandQS - Randomisierte quicksort - wobei der Schwenk, zum Unterteilen des Satzes in zwei Teile verwendet wird , wird nach dem Zufallsprinzip ausgewählt.

Ich habe seit einiger Zeit mein (zugegebenermaßen etwas unterbewertetes) Gehirn darüber geärgert, aber ich konnte nicht erkennen, welchen Vorteil dieser Algorithmus gegenüber dem einfachen Auswählen beispielsweise des mittleren Elements (im Index, nicht in der Größe) jedes Mal hat.

Ich nehme an, ich kann Folgendes nicht sehen: Wenn die ursprüngliche Menge in zufälliger Reihenfolge vorliegt, was ist der Unterschied zwischen dem Auswählen eines Elements an einer zufälligen Position in der Menge und dem Auswählen eines Elements an einer festen Position?

Kann mich jemand ziemlich einfach aufklären?

algorithm-analysis sorting randomized-algorithms Brent.Longborough
quelle

Antworten:

19

Wenn das Eingabearray gleichmäßig nach dem Zufallsprinzip verteilt ist, gibt es (wie Sie bemerkt haben) keinen Unterschied, ob Sie ein Element immer an einer festen Position auswählen (z. B. das mittlere, wie Sie vorschlagen) oder ein zufällig ausgewähltes Element.

Wenn Ihr Eingabearray jedoch nicht wirklich in zufälliger Reihenfolge vorliegt (was in fast allen praktischen Szenarien der Fall ist), müssen Sie das Array entweder "vormischen", damit die darin enthaltenen Elemente in zufälliger Reihenfolge platziert werden, oder ( äquivalent) nehmen Sie immer ein zufälliges Element als Dreh- und Angelpunkt. Dies stellt sicher, dass die Partitionierungsphase von QuickSort die Arrays in Sub-Arrays nahezu gleicher Größe partitioniert und somit die erwartete Laufzeit bleibt.O(nlog⁡n)

Ihre Verwirrung scheint also auf die Tatsache zurückzuführen zu sein, dass Sie in der Praxis davon ausgehen können, dass das Eingabearray immer zufällig verteilt ist.

Jernej
quelle
7
Es kann erwähnenswert sein, dass es zwar eine theoretische Garantie für die Zufallsgenerierung gibt (da anstelle von ) angezeigt wird), die Daten jedoch vor dem Zufallsprinzip zu einer praktischen Beschleunigung führen kann. Schlechte Quicksort-Fälle sind häufiger als erwartet (offensichtlich abhängig von der Implementierung). O(nlog⁡n)O(n2)
SamM,
Wenn Sie "gleichmäßig nach dem Zufallsprinzip verteilt" sagen , bedeutet dies, dass jedes derPermutationen haben die gleiche Wahrscheinlichkeit von ? n!1n!
Robert S. Barnes
@ RobertS.Barnes Ja
Jernej
4

Wie von Jernej bemerkt, gilt die Annahme, dass alle Permutationen der Eingabe gleich wahrscheinlich sind, nicht immer in der Realität. Die erste Idee könnte sein, das Eingabearray zu permutieren. Dies würde funktionieren, aber es ist einfacher, die Situation zu analysieren, in der ein Drehpunkt zufällig ausgewählt wird. Dies wird auch als Zufallsstichprobe bezeichnet .

Juho
quelle