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?
fuente
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 .
fuente