¿Podemos hacer una clasificación rápida con n log la peor complejidad de caso?

Me preguntaba si de alguna manera podemos modificar el algoritmo de ordenación rápida para producir la peor complejidad de tiempo de caso de O (n logn). Aunque esto se puede hacer permutando datos y luego suponiendo que obtendremos la complejidad promedio de casos en lugar del peor de los casos. Pero esta no es una solución completa, ya que podemos volver a caer en el peor de los casos después de la permutación. ¿Hay alguna otra forma de evitarlo?¿Podemos hacer una clasificación rápida con n log la peor complejidad de caso?

Fuente

2012-03-01 pseudocode

Una manera trivial es agregar dos líneas a la parte superior de la función: una que hace una ordenación de acumulación o fusión, y la segunda de las cuales regresa. Entiendo que esto probablemente no es lo que tenía en mente, pero espero que esto ilustre que va a necesitar ser más específico sobre qué tipo de "modificaciones" están permitidas en el algoritmo estándar de quicksort ... va a tiene que ser bastante preciso en sus limitaciones para hacer algo que he sugerido fuera de los límites. – Patrick87

Estaba pensando si de alguna manera podemos modificar la clasificación rápida en sí misma. Como poner algunas restricciones en el pivote. Solo puedo usar el tipo de fusión en lugar de la ordenación rápida, en lugar de utilizar varios géneros. Estoy buscando algunos ajustes solo en Quick sort. – pseudocode

Ver: http://stackoverflow.com/a/70631/44522 – MicSim

Bueno, sí podemos bajarlo a O (nlogn). Todos los algoritmos que he visto que intentan reducir esto se basan en elegir su punto de pivote. Si puede elegir "inteligentemente" su punto de pivote, puede bajarse.

Opciones 1. Intro Sort. Ya no es un tipo rápido "puro" ahora. Utiliza el tipo de fusión más adelante. 2. Elegir la mediana como pivote. Ahora, encontrar la mediana puede llevar una gran cantidad de tiempo si se hace de la manera habitual, PERO hay una mención en el Introduction to Algorithms.

Aquí es algo directamente de la boca del caballo Introduction to Algorithms

Divide la matriz en [/ n 5] grupos con cada grupo que tiene 5 elementos
Encuentra mediana de cada grupo mediante la ordenación por inserción y luego recoger la mediana de esta lista
Luego tendrá que intentar de forma recursiva y encontrar la mediana de [n/5] medianas calculadas de cada grupo.
partición de la matriz alrededor de este medio

hay algunas cosas más complejas en este algoritmo que he escondido. Puede revisarlo en el mismo libro si lo desea. Por lo general, no trato de usar este algoritmo. Utilizo una operación de selección aleatoria para encontrar el pivote y trabajar con eso.

Fuente

2012-03-01 16:36:00

Gracias S.P. Supongo que esto es lo que estaba buscando. – pseudocode

+1 para mencionar la mediana de las medianas de CLRS – Adrian

Para la opción 1, no es una ordenación por fusión sino una ordenación por montones a la que cambia el acceso rápido. Desea conservar la propiedad in situ de quicksort. Por razones de rendimiento, el tipo de fusión rara vez se implementa en el lugar, aunque podría serlo. – user515430

Bueno, "modificar" es una palabra bastante subjetiva aquí. Hay varias maneras en que puede aumentar el quicksort para que se ejecute en O(n log n). Aún se puede determinar si se puede llamar de una manera rápida o no.

Uno de los cuales es introsort. Introsort comienza con quicksort pero luego cambia a merge sort, que tiene la peor complejidad de caso O(n log n). Uno de los propósitos de introsort es combatir la mediana de 3 listas de asesinos.

Fuente

2012-03-01 16:36:38 tskuzzy

Gracias tskuzzy. Esto ayudará.. – pseudocode

¿Podemos hacer una clasificación rápida con n log la peor complejidad de caso?

Respuesta

Cuestiones relacionadas