¿Por qué se usa quicksort en la práctica?

Question

Quicksort tiene un rendimiento en el peor de los casos de O (n), pero todavía se usa ampliamente en la práctica. ¿Por qué es esto?

Answer 1

Porque en promedio es la clase de comparación más rápida (en términos de tiempo transcurrido).

Answer 2

Porque, en el caso general, es uno de los algoritmos de clasificación más rápidos.

Answer 3

El orden asintótico medio de QuickSort es O(nlogn) y suele ser más eficiente que heapsort debido a constantes más pequeñas (bucles más ajustados). De hecho, hay un algoritmo teórico de selección de mediana de tiempo lineal que puede usar para encontrar siempre el mejor pivote, lo que resulta en el peor de los casos O(nlogn). Sin embargo, el QuickSort normal suele ser más rápido que este teórico.

para que sea más sensible, considerar la probabilidad de que QuickSort terminará en O(n2). Es solo 1/n! lo que significa que casi nunca encontrará ese mal caso.

Answer 4

No debe centrarse solo en el peor de los casos y solo en la complejidad del tiempo. Es más sobre el promedio que el peor, y ya es hora y espacio.

Quicksort:

• tiene complejidad del tiempo promedio de Θ (n registro n);
• se puede implementar con complejidad de espacio de Θ (log n);

Tenga también en cuenta que la notación O grande no tiene en cuenta las constantes, pero en la práctica sí hace la diferencia si el algoritmo es pocas veces más rápido. Θ (n registro n) significa, que el algoritmo se ejecuta en K   n   log (n), donde K es constante. Quicksort es el algoritmo de comparación-clasificación con el K más bajo.

Answer 5

Puede valer la pena señalar que C tiene la función de biblioteca qsort(), pero no es necesario que se implemente utilizando un QuickSort real, que depende del proveedor del compilador.

Answer 6

Además de ser el más rápido, algunos de sus malos escenarios pueden evitarse mezclando la matriz antes de ordenarla. En cuanto a su debilidad con pequeños conjuntos de datos, obviamente no es un gran problema ya que los conjuntos de datos son pequeños y el tiempo de ordenamiento es probablemente pequeño independientemente.

Como ejemplo, escribí una función python para QuickSort y tipos de burbujas. La clasificación de burbuja tarda ~ 20 segundos para ordenar 10.000 registros, 11 segundos para 7500 y 5 para 5000. ¡El quicksort hace todo esto en alrededor de 0.15 segundos!

Answer 7

Curiosamente, quicksort realiza más comparaciones en promedio que mergesort - 1.44 n lg n (esperado) para quicksort versus n lg n para mergesort.Si todo lo que importaba fueran las comparaciones, mergesort sería muy preferible a quicksort.

La razón de que el quicksort sea rápido es que tiene muchas otras propiedades deseables que funcionan extremadamente bien en hardware moderno. Por ejemplo, quicksort no requiere asignaciones dinámicas. Puede funcionar in situ en la matriz original, utilizando solo el espacio de la pila O (log n) (el peor de los casos, si se implementa correctamente) para almacenar los marcos de la pila necesarios para la recursión. Aunque se puede hacer que mergesort haga esto, hacerlo suele tener una gran penalización de rendimiento durante el paso de fusión. Otros algoritmos de clasificación como heapsort también tienen esta propiedad.

Además, quicksort tiene una ubicación excelente de referencia. El paso de partición, si se hace usando el algoritmo de partición en el lugar de Hoare, es esencialmente dos escaneos lineales realizados hacia adentro desde ambos extremos de la matriz. Esto significa que quicksort tendrá una cantidad muy pequeña de errores de caché, lo que en las arquitecturas modernas es crítico para el rendimiento. Heapsort, por otro lado, no tiene una localidad muy buena (salta alrededor de una matriz), aunque la mayoría de las implementaciones de mergesort tienen una localidad razonable.

Quicksort también es muy paralelizable. Una vez que se ha producido el paso de partición inicial para dividir la matriz en regiones más pequeñas y más grandes, esas dos partes se pueden ordenar de forma independiente una de la otra. Muchos algoritmos de clasificación pueden ser paralelizados, incluyendo mergesort, pero el rendimiento de la solución rápida paralela tiende a ser mejor que otros algoritmos paralelos por la razón anterior. Heapsort, por otro lado, no.

El único problema con el quicksort es la posibilidad de que se degrade a O (n), lo que en grandes conjuntos de datos puede ser muy serio. Una forma de evitar esto es hacer que el algoritmo se introspectivamente y cambiar a uno de los algoritmos más lentos pero más confiables en el caso de que degenere. Este algoritmo, llamado introsort, es un gran algoritmo de clasificación híbrido que obtiene muchos de los beneficios de la conexión rápida sin el caso patológico.

En resumen:

• Quicksort es en el lugar a excepción de los marcos de pila utilizados en la recursión, que tienen O (log n) el espacio.
• Quicksort tiene buena localidad de referencia.
• Quicksort se paraleliza fácilmente.

Esto explica por qué el quicksort tiende a superar los algoritmos de ordenación que en papel podrían ser mejores.

Espero que esto ayude!

Answer 8

Bcs este es uno de Algoritmo que funciona bien en grandes conjuntos de datos con complejidad O (NlogN). Este también es un algoritmo que ocupa espacio constante. Al seleccionar el elemento pivote con prudencia, podemos evitar el peor caso de clasificación rápida y funcionará en O (NlogN) siempre incluso en una matriz ordenada.