Como sabemos, el rendimiento de la cadena rápida es O (n * log (n)) en promedio, pero el rendimiento de fusión y heapsort es O (n * log (n)) en promedio también. Entonces, la pregunta es por qué el quicksort es más rápido en promedio.¿Por qué el quicksort es más rápido en promedio que otros?
Peor caso de ordenación rápida es en realidad peor que heapsort y mergesort, pero quicksort es más rápido en promedio.
cuanto a por qué, se necesitará tiempo para explicar y por lo tanto me referiré a Skiena, The algorithm design manual.
Una cita que resume la clasificación rápida vs fusión/heapsort:
Cuando se enfrentan con los algoritmos de la misma asintótica complejidad, implementación detalles y peculiaridades del sistema como el rendimiento de la memoria caché y el tamaño de la memoria pueden demostrar ser el factor decisivo. Lo que podemos decir es que los experimentos muestran que cuando se implementa bien una ruta de acceso rápido correctamente implementada, generalmente es 2-3 veces más rápido que el conjunto de conexiones mergesort o . La razón principal es que las operaciones en el bucle más interno son más simples. Pero no puedo discutir con usted si no me cree cuando digo quicksort es más rápido. Es una pregunta cuya solución se encuentra fuera de las herramientas analíticas que estamos utilizando. La mejor manera de saberlo es implementar algoritmos y experimentar.
Típicamente, quicksort es significativamente más rápido en la práctica que otras O (nlogn) algoritmos, ya que su bucle interior puede ser implementado de manera eficiente en la mayoría de arquitecturas, y en la mayoría del mundo real datos, es posible hacer elecciones de diseño que minimicen la probabilidad de requerir tiempo cuadrático. Además, quicksort tiende a hacer excelente uso de la jerarquía de memoria , aprovechando al máximo la memoria virtual y las memorias caché disponibles. Aunque el quicksort no es una ordenación in situ y utiliza memoria auxiliar, es muy adecuado para las arquitecturas modernas de la computadora .
También eche un vistazo a comparison with other sorting algorithms en la misma página.
Vea también Why is quicksort better than other sorting algorithms in practice? en el sitio de CS.
¿Sabes exactamente cómo "aprovecha la memoria virtual y el caché"? ¿Algún ejemplo? – Michael
si está pensando en términos de algoritmo, no se preocupe por la memoria virtual y el caché. los algoritmos no dependen del hardware. – DarthVader
El algoritmo atraviesa secuencialmente lo que lo convierte en una buena 'localidad de referencia' (http: //en.wikipedia.org/wiki/Locality_of_reference) que hace que su caché funcione bien (y así acelerar el trabajo) – ChristopheD
Timsort puede ser una opción better ya que está optimizada para el tipo de datos que se ven al ordenar en general, en el lenguaje Python donde los datos a menudo contienen "corridas" incrustadas de elementos previamente seleccionados. Recientemente también ha sido adoptado por Java.
+1 por el interesante enlace a Timsort. –
heapsort es O (n * log (n)) en el peor de los casos, probablemente en todos los casos. – phkahler