Jakie są zalety Randomized Quicksort?

W książce algorytmy randomizowane , Motwani i Raghavan otworzyć zapoznaniu się z opisem ich funkcji RandQS - randomizowane Quicksort - przy czym czop, służy do podziału zbioru na dwie części, jest wybierana losowo.

Przez jakiś czas dręczyłem nad tym (co prawda trochę słabe) mózgi, ale nie byłem w stanie zobaczyć, jaką przewagę ma ten algorytm nad prostym wybieraniem, powiedzmy, środkowego elementu (indeks, a nie rozmiar) za każdym razem.

Przypuszczam, że nie widzę tego: jeśli początkowy zestaw jest w losowej kolejności, jaka jest różnica między wybieraniem elementu w losowej lokalizacji w zestawie a wybieraniem elementu w ustalonej pozycji?

Czy ktoś może mnie oświecić w dość prosty sposób?

Jeśli tablica wejściowa jest rozmieszczona losowo równomiernie, to (jak zauważyłeś) nie ma różnicy między zawsze wybieraniem elementu w ustalonej pozycji (na przykład środkowym, jak sugerujesz) lub wybieraniem elementu wybranego losowo.

Jeśli jednak tablica wejściowa nie jest tak naprawdę w przypadkowej kolejności (co zdarza się w prawie wszystkich praktycznych scenariuszach), należy albo „wstępnie odświeżyć” tablicę, aby elementy w niej były ustawione w losowej kolejności, lub ( równoważnie) zawsze bierz losowy element jako oś przestawną. Zapewnia to fazę partycjonowania Quicksort, która dzieli tablice na podobszary o niemal równej wielkości, a zatem oczekiwany czas działania pozostaje $O(n\log n)$

Twoje zamieszanie wydaje się wynikać z faktu, że w jakiś sposób zakładasz, że algorytm sortowania może (w praktyce) oczekiwać, że tablica wejściowa będzie zawsze losowo rozmieszczona.

Jak zauważył Jernej, założenie, że wszystkie permutacje danych wejściowych są jednakowo prawdopodobne, nie zawsze jest prawdziwe. Pierwszym pomysłem może być permutacja tablicy wejściowej. To by działało, ale łatwiej jest przeanalizować sytuację, w której oś jest wybierana losowo. Jest to również znane jako losowe próbkowanie .