El peor caso para la clasificación rápida es cuando selecciona un pivote que es el número más pequeño en el rango o el número más grande en el rango. ¿Por qué?
Sea [math] T (n) [/ math] la cantidad de trabajo necesaria para ejecutar la clasificación rápida en números [math] n [/ math]. En este caso, nuestro pivote nos da subrangos de tamaño [matemática] 0 [/ matemática] y [matemática] n-1 [/ matemática], por lo que tenemos una recurrencia que es [matemática] T (n) = T (0) + T (n-1) + O (n) [/ matemática], que tiene solución [matemática] T (n) = O (n ^ 2) [/ matemática].
Una razón informal por la cual quicksort se ejecuta en [math] O (n \ log n) [/ math] en expectativa es que el pivote, en expectativa, divide el rango dado en dos subranges algo equilibrados. Puede probar que incluso si la división es [matemática] \ dfrac {n} {100} [/ matemática] y [matemática] \ dfrac {99n} {100} [/ matemática] o incluso fracciones constantes más absurdas de [matemática] n [/ math], quicksort todavía se ejecuta en [math] O (n \ log n) [/ math].
- ¿Cómo es PDPU para CS?
- ¿Son todos los 500 mejores supercomputadores iguales, en términos de computación?
- ¿Qué es mejor: CS en KJ Somiaya o IT en DJ Sanghvi?
- Si el universo es abierto / plano y sufre una muerte fría en expansión, ¿la cantidad total de cómputo que se puede realizar es finita?
- Deseo recibir notificaciones push en mi computadora con Windows 7. ¿Qué software me puede ayudar a lograr esto?
Entonces la pregunta sigue siendo, ¿puedes forzar la ejecución rápida en [math] O (n ^ 2) [/ math]?
Si quicksort se implementa de manera no determinista, entonces NO . No puede garantizar que las selecciones de pivote sean malas para cada llamada.
Si quicksort se implementa de manera determinista con una selección ingenua del pivote, la respuesta es SÍ (sin embargo, vea la respuesta de Anand Oza para obtener una respuesta NO ). Como puede seleccionar la configuración original de la matriz, puede seleccionar un pivote que genera una división que es [matemática] 0 [/ matemática] y [matemática] n-1 [/ matemática]. Luego, en la división [matemática] n-1 [/ matemática], puede organizar esos números de modo que el pivote genere la peor división posible. Continúe esto hasta el final.
Resulta que esto es un gran problema para los codificadores de Java que están ordenando matrices primitivas. Hace unos meses, alguien descubrió cómo hacer que Java 7 QuickSort se ejecute en [math] O (n ^ 2) [/ math] time (consulte [Java] Java 7 Quicksort Killer – Pastebin.com para más detalles). Esto causó que los codificadores de Java que estaban clasificando matrices primitivas tuvieran que barajar sus matrices de entrada o convertirlas en objetos de clasificación, lo que se hace con mergesort en su lugar (esto se hace en el contexto de concursos de programación, donde se espera que se ejecuten muchos algoritmos en [ matemática] O (n \ log n) [/ matemática] con la sobrecarga de la clasificación, por lo que se necesita una ordenación [matemática] O (n \ log n) [/ matemática] sobre una [matemática] O (n ^ 2) [ / math] sort).
