Un hecho importante que debe saber es que en una matriz de elementos distintos, el quicksort con una elección aleatoria de partición se ejecutará en O (n lg n). Hay muchas buenas pruebas de esto, y the one on Wikipedia en realidad tiene una discusión bastante buena de esto. Si está dispuesto a buscar una prueba un poco menos formal que sea matemáticamente sólida, la intuición es la siguiente. Cada vez que elijamos un pivote, digamos que un pivote "bueno" es un pivote que nos da al menos una división de 75%/25%; es decir, es mayor que al menos el 25% de los elementos y, como máximo, el 75% de los elementos. Queremos consolidar el número de veces que podemos obtener un pivote de este tipo antes de que termine el algoritmo. Supongamos que obtenemos k divisiones de este tipo y consideramos el tamaño del subproblema más grande generado de esta manera. Tiene un tamaño como máximo (3/4) k n, ya que en cada iteración nos estamos deshaciendo de al menos un cuarto de los elementos. Si consideramos el caso específico donde k = log 3/4 (1/n) = log 4/3 n, entonces el tamaño del subproblema más grande después de que se elijan k buenos pivotes será 1, y la recursión detener. Esto significa que si elegimos obtener O (lg n) buenos pivotes, la recursión terminará. Pero en cada iteración, ¿cuál es la posibilidad de obtener ese pivote? Bueno, si elegimos el pivote al azar, entonces hay un 50% de probabilidad de que esté en el medio 50% de los elementos, y así sucesivamente, elegiremos dos pivotes aleatorios antes de obtener un buen pivote. Cada paso de elegir un pivote toma O (n) tiempo, por lo que debemos pasar aproximadamente O (n) tiempo antes de obtener cada pivote. Como obtenemos como máximo O (lg n) buenos pivotes, el tiempo de ejecución general es O (n lg n) según las expectativas.
Un detalle importante en la discusión anterior es que si reemplaza la división del 75% con una división constante, es decir, una división de (100% k/k%), el análisis asintótico es el mismo. Obtendrá que la quicksort tome, en promedio, O (n lg n) tiempo.
La razón por la que mencioné esta prueba es porque te da un buen marco para pensar cómo elegir un pivote en la oferta rápida. Si puede elegir un pivote que esté bastante cerca del centro en cada iteración, puede garantizar el tiempo de ejecución O (n lg n).Si no puede garantizar que obtendrá un buen pivote en cualquier iteración, pero puede decir que con la expectativa solo requiere un número constante de iteraciones antes de obtener un buen pivote, entonces también puede garantizar O (n lg n) tiempo de ejecución esperado
Dado esto, echemos un vistazo a sus esquemas de pivote propuestos. Para (a), si la matriz es aleatoria, elegir el primer elemento como pivote es esencialmente lo mismo que elegir un pivote aleatorio en cada paso, y así, mediante el análisis anterior, obtendrás O (n lg n) en tiempo de ejecución con expectativas . Para (b), si sabes que la matriz está ordenada en su mayoría, elegir la mediana es una buena estrategia. La razón es que si podemos decir que cada elemento está "bastante cerca" de donde debería estar en la secuencia ordenada, entonces puedes argumentar que cada pivote que elijas es un buen pivote, dándote la O (n lg n) tiempo de ejecución que desee. (El término "bastante cerca" no es matemáticamente preciso, pero creo que podrías formalizar esto sin demasiada dificultad si quisieras).
En cuanto a (c) y (d), de los dos, (d) es el único garantizado para obtener O (n lg n) en la expectativa. Si determinísticamente eliges ciertos elementos para utilizarlos como pivotes, tu algoritmo será vulnerable a las secuencias determinísticas que pueden degenerarlo en el comportamiento O (n). De hecho, McIlroy cuenta con un documento realmente interesante llamado "A Killer Adversary for Quicksort" que describe cómo puede tomar cualquier ruta de acceso determinista y construir la peor entrada de un caso patológico mediante una función de comparación maliciosa. Es casi seguro que desea evitar esto en cualquier implementación de quicksort real, ya que de lo contrario los usuarios maliciosos podrían lanzar ataques DoS contra su código alimentando estas secuencias asesinas para forzar a su programa a ordenar en tiempo cuadrático y así colgar. Por otro lado, debido a que (d) está escogiendo sus puntos de muestra aleatoriamente, no es vulnerable a este ataque, porque en cualquier secuencia la elección de los pivotes es aleatoria.
Aunque, curiosamente, para (d), aunque no hace daño elegir tres elementos aleatorios y tomar la mediana, no es necesario que haga esto. La prueba anterior es suficiente para mostrar que obtendrá O (n lg n) en la expectativa con una única opción de pivote aleatorio. De hecho, no sé si elegir la mediana de tres valores aleatorios mejorará el rendimiento del algoritmo de la solución rápida, aunque dado que el quicksort es siempre Ω (n lg n) ciertamente no será mejor que seleccionar elementos aleatorios como el pivotes.
Espero que esto ayude un poco. Me encanta el algoritmo de solución rápida y todas las decisiones de diseño involucradas en la construcción de una buena implementación de quicksort. :-)
No entiendo la pregunta. –
P: Para las posibles estrategias que he elegido (a-d) ¿cómo afectarán el comportamiento general del algoritmo de la solución rápida? –