¿Cuál es la ventaja de Randomized Quicksort?

18

En su libro Algoritmos aleatorios , Motwani y Raghavan abren la introducción con una descripción de su función RandQS - Randomized quicksort - donde el pivote, utilizado para dividir el conjunto en dos partes, se elige al azar.

He estado estacionando mis cerebros (ciertamente algo poco poderosos) sobre esto durante algún tiempo, pero no he podido ver qué ventaja tiene este algoritmo sobre simplemente elegir, por ejemplo, el elemento medio (en el índice, no el tamaño) cada vez.

Supongo que lo que no puedo ver es esto: si el conjunto inicial está en un orden aleatorio, ¿cuál es la diferencia entre elegir un elemento en una ubicación aleatoria en el conjunto y elegir un elemento en una posición fija?

¿Puede alguien iluminarme, en términos bastante simples?

Brent.Longborough
fuente

Respuestas:

19

Si la matriz de entrada se distribuye de manera uniforme al azar, entonces (como notó) no hay diferencia entre elegir siempre un elemento en una posición fija (por ejemplo, la del medio como sugiere) o elegir un elemento elegido al azar.

Sin embargo, si su matriz de entrada no está realmente en orden aleatorio (que es el caso en casi todos los escenarios prácticos), entonces uno debe "pre-mezclar" la matriz para que los elementos en ella se coloquen en orden aleatorio, o ( equivalente) siempre tome un elemento aleatorio como pivote. Esto garantiza la fase de partición de particiones de ordenación rápida de las matrices en sub-matrices de casi el mismo tamaño y, por lo tanto, el tiempo de ejecución esperado sigue siendoO(norteIniciar sesiónnorte)

Entonces, su confusión parece provenir del hecho de que de alguna manera asume que un algoritmo de clasificación puede (en la práctica) esperar que la matriz de entrada siempre se distribuya aleatoriamente.

Jernej
fuente
77
Vale la pena mencionar que si bien existe una garantía teórica de aleatorizar (porque obtienes peor de los casos en lugar de ), los datos de aleatorización previa pueden conducir a aceleraciones prácticas también en algunas aplicaciones. Los casos de clasificación rápida incorrectos son más comunes de lo que cabría esperar (dependiendo obviamente de la implementación). O(norteIniciar sesiónnorte)O(norte2)
SamM
Cuando dice "distribuido uniformemente al azar" , quiere decir que cada una de laspermutaciones tiene la misma probabilidad de ? norte!1norte!
Robert S. Barnes
@ RobertS.Barnes Sí
Jernej
4

Como señaló Jernej, la suposición de que todas las permutaciones de la entrada son igualmente probables no siempre se cumple en la realidad. La primera idea podría ser permutar la matriz de entrada. Esto funcionaría, pero es más fácil analizar la situación en la que se elige un pivote al azar. Esto también se conoce como muestreo aleatorio .

Juho
fuente