Esta es una buena pregunta, porque ambos algoritmos cuentan con una complejidad de caso O (n * log n) promedio. Sin embargo, la complejidad del peor caso de heapsort [1] es Θ (n * log n) y la complejidad del mejor de los casos también es la misma, mientras que quicksort [2] tiene Θ (n ^ 2). Entonces, ¿por qué la clasificación rápida se considera mejor, cuando en teoría debería ser peor?
Los resultados prácticos muestran que tener una mejor complejidad teórica no lo es todo en el mundo de los algoritmos de clasificación [3] [4], y algunas fuentes [5] citan tres veces la eficiencia de los tipos de fusión y almacenamiento dinámico. Sin embargo, hay estudios [6] [7] que citan el resultado opuesto de que el montón es más rápido en un caso promedio. Para satisfacer a ambos lados, incluso existe un algoritmo [8] que cambia de clasificación rápida a clasificación múltiple si se detecta un caso particularmente malo para la clasificación rápida.
Además, el ordenamiento rápido tiene un factor constante alto en la complejidad, por lo que en el caso de las entradas pequeñas, es preferible el tipo de inserción [9] y debe usarse.
- ¿Cuál es la mejor manera de encontrar la media de una secuencia en cualquier momento?
- ¿Cuál es la forma correcta de leer CLRS (Introducción a los algoritmos)?
- ¿Por qué no es posible encontrar la ruta más corta desde el vértice de origen a cualquier otro vértice si el gráfico contiene un ciclo?
- ¿Puedo adoptar un enfoque de alto nivel para aprender Machine Learning sin molestar a los matemáticos detrás de los algoritmos de ML?
- Cómo encontrar a alguien que pueda implementar un algoritmo de enrutamiento de vehículos que se nos ocurrió
La conclusión es difícil de hacer, ya que este es un tema de debate considerable. Te animo a que leas algunas de las fuentes que he vinculado, que hagas algunos puntos de referencia con tu biblioteca favorita que implementa estos algoritmos y, aunque la mayoría parece aceptar la clasificación rápida como el rey, para mantener tu propio consejo.
Notas al pie
[1] Heapsort – Wikipedia
[2] Quicksort – Wikipedia
[3] Algoritmo de clasificación – Wikipedia
[4] Clasificación rápida vs montón
[5] El manual de diseño de algoritmos
[6] Heapsort, Quicksort y Entropy
[7] Clasificación revisitada
[8] Introsort – Wikipedia
[9] Clasificación rápida vs montón
