En un curso de algoritmos estándar se nos enseña que quicksort es en promedio y en el peor de los casos. Al mismo tiempo, se estudian otros algoritmos de clasificación que son en el peor de los casos (como mergesort y heapsort ), e incluso tiempo lineal en el mejor de los casos (como bubbleort ) pero con algunas necesidades adicionales de memoria.O ( n 2 ) O ( n log n $O(n \log n)$$O(n^2)$$O(n \log n)$

Después de un rápido vistazo a algunos tiempos de ejecución más , es natural decir que quicksort no debería ser tan eficiente como otros.

Además, tenga en cuenta que los estudiantes aprenden en los cursos de programación básica que la recursividad no es realmente buena en general porque podría usar demasiada memoria, etc. Por lo tanto (y aunque esto no es un argumento real), esto da la idea de que la clasificación rápida podría no ser realmente bueno porque es un algoritmo recursivo.

¿Por qué, entonces, la clasificación rápida supera a otros algoritmos de clasificación en la práctica? ¿Tiene que ver con la estructura de los datos del mundo real ? ¿Tiene que ver con la forma en que funciona la memoria en las computadoras? Sé que algunos recuerdos son mucho más rápidos que otros, pero no sé si esa es la verdadera razón de este rendimiento contraintuitivo (en comparación con las estimaciones teóricas).

Actualización 1: una respuesta canónica dice que las constantes involucradas en el del caso promedio son más pequeñas que las constantes involucradas en otros algoritmos . Sin embargo, todavía tengo que ver una justificación adecuada de esto, con cálculos precisos en lugar de solo ideas intuitivas.O ( n log n $O(n\log n)$$O(n\log n)$

En cualquier caso, parece que la diferencia real ocurre, como sugieren algunas respuestas, a nivel de memoria, donde las implementaciones aprovechan la estructura interna de las computadoras, utilizando, por ejemplo, que la memoria caché es más rápida que la RAM. La discusión ya es interesante, pero aún me gustaría ver más detalles con respecto a la administración de memoria, ya que parece que la respuesta tiene que ver con eso.

Actualización 2: hay varias páginas web que ofrecen una comparación de algoritmos de clasificación, algunas más elegantes que otras (más notablemente sorting-algorithms.com ). Aparte de presentar una buena ayuda visual, este enfoque no responde a mi pregunta.

Respuesta corta

El argumento de eficiencia de caché ya se ha explicado en detalle. Además, hay un argumento intrínseco, por qué Quicksort es rápido. Si se implementa como con dos "punteros de cruce", por ejemplo , aquí , los bucles internos tienen un cuerpo muy pequeño. Como este es el código ejecutado con mayor frecuencia, vale la pena.

Respuesta larga

Ante todo,

¡El caso promedio no existe!

Como el mejor y el peor de los casos a menudo son extremos que rara vez ocurren en la práctica, se realiza un análisis de caso promedio. ¡Pero cualquier análisis de caso promedio supone una distribución de entradas ! Para la clasificación, la opción típica es el modelo de permutación aleatoria (asumido tácitamente en Wikipedia).

¿Por qué -Notation?$O$

El descarte de constantes en el análisis de algoritmos se realiza por una razón principal: si estoy interesado en tiempos de ejecución exactos , necesito costos (relativos) de todas las operaciones básicas involucradas (incluso ignorando los problemas de almacenamiento en caché, canalización en procesadores modernos ...). El análisis matemático puede contar con qué frecuencia se ejecuta cada instrucción, pero los tiempos de ejecución de instrucciones individuales dependen de los detalles del procesador, por ejemplo, si una multiplicación entera de 32 bits requiere tanto tiempo como la suma.

Hay dos salidas:

1. Arreglar algún modelo de máquina.

   Esto se hace en la serie de libros de Don Knuth "El arte de la programación de computadoras" para una computadora artificial "típica" inventada por el autor. En el volumen 3 encontrará resultados de casos promedio exactos para muchos algoritmos de clasificación, por ejemplo

   • Clasificación rápida : $11.667(n+1)\ln(n)-1.74n-18.74$
   • Mergesort: $12.5 n \ln(n)$
   • Heapsort: $16 n \ln(n) +0.01n$
   • Insertionsort: ^{[ fuente ]}$2.25n^2+7.75n-3ln(n)$
     

   Estos resultados indican que Quicksort es el más rápido. Pero, solo se prueba en la máquina artificial de Knuth, no necesariamente implica nada, por ejemplo, su PC x86. Tenga en cuenta también que los algoritmos se relacionan de manera diferente para entradas pequeñas:
   
   ^{[ fuente ]}

2. Analizar operaciones básicas abstractas .

   Para la ordenación basada en la comparación, generalmente se trata de intercambios y comparaciones clave . En los libros de Robert Sedgewick, por ejemplo, "Algoritmos" , se sigue este enfoque. Te encuentras ahi

   • Quicksort: comparaciones y $2n\ln(n)$intercambios en promedio$\frac13n\ln(n)$
   • Mergesort: comparaciones, pero hasta 8.66 n ln ( n ) accesos de matriz (mergesort no se basa en el intercambio, por lo que no podemos contar eso).$1.44n\ln(n)$$8.66n\ln(n)$
   • Insertionsort: comparaciones y$\frac14n^2$swaps en promedio.$\frac14n^2$

   Como puede ver, esto no permite fácilmente comparaciones de algoritmos como el análisis exacto del tiempo de ejecución, pero los resultados son independientes de los detalles de la máquina.

Otras distribuciones de entrada

Como se señaló anteriormente, los casos promedio son siempre con respecto a alguna distribución de entrada, por lo que uno podría considerar otros que no sean permutaciones aleatorias. Por ejemplo, se ha realizado una investigación para Quicksort con elementos iguales y hay un buen artículo sobre la función de clasificación estándar en Java

Hay varios puntos que se pueden hacer con respecto a esta pregunta.

Quicksort suele ser rápido

Aunque Quicksort tiene el comportamiento peor de los casos , generalmente es rápido: suponiendo una selección de pivote aleatorio, existe una gran posibilidad de que elijamos algún número que separe la entrada en dos subconjuntos de tamaño similar, que es exactamente lo que queremos tener .$O(n^2)$

En particular, incluso si elegimos un pivote que crea una división del 10% -90% cada 10 divisiones (que es una división meh), y una división de 1 elemento - elemento de lo contrario (que es la peor división que puede obtener) , nuestro tiempo de ejecución sigue siendo O ( n log n ) (tenga en cuenta que esto haría explotar las constantes hasta un punto en el que Merge sort es probablemente más rápido).$n-1$$O(n \log n)$

Quicksort suele ser más rápido que la mayoría de los tipos

El ordenamiento rápido suele ser más rápido que los tipos que son más lentos que (por ejemplo, ordenación por inserción con su tiempo de ejecución O ( n 2 ) ), simplemente porque durante grandes n explotan sus tiempos de ejecución.$O(n \log n)$$O(n^2)$$n$

Una buena razón por la cual Quicksort es tan rápido en la práctica en comparación con la mayoría de los otros algoritmos como Heapsort, es porque es relativamente eficiente en caché. Su tiempo de ejecución es en realidad O ( $O(n \log n)$, dondeBes el tamaño del bloque. Heapsort, por otro lado, no tiene tal aceleración: no está accediendo de manera eficiente a la memoria caché.$O(\frac{n}{B} \log (\frac{n}{B}))$$B$

La razón de esta eficiencia de caché es que escanea linealmente la entrada y particiona linealmente la entrada. Esto significa que podemos aprovechar al máximo cada carga de caché que hacemos mientras leemos cada número que cargamos en el caché antes de cambiar ese caché por otro. En particular, el algoritmo es ajeno a la memoria caché, lo que proporciona un buen rendimiento de memoria caché para cada nivel de memoria caché, que es otra ganancia.

La eficiencia del caché podría mejorarse aún más a , dondeMes el tamaño de nuestra memoria principal, si usamosk-way Quicksort. Tenga en cuenta que Mergesort también tiene la misma eficiencia de caché que Quicksort, y su versión k-way de hecho tiene un mejor rendimiento (a través de factores constantes más bajos) si la memoria es una restricción severa. Esto da lugar al siguiente punto: tendremos que comparar Quicksort con Mergesort en otros factores.$O(\frac{n}{B} \log_{\frac{M}{B}} (\frac{n}{B}))$$M$$k$

Quicksort suele ser más rápido que Mergesort

Esta comparación es completamente sobre factores constantes (si consideramos el caso típico). En particular, la elección es entre una elección subóptima del pivote para Quicksort versus la copia de toda la entrada para Mergesort (o la complejidad del algoritmo necesario para evitar esta copia). Resulta que el primero es más eficiente: no hay ninguna teoría detrás de esto, simplemente es más rápido.

Tenga en cuenta que Quicksort realizará más llamadas recursivas, pero asignar espacio en la pila es barato (de hecho, casi gratis, siempre y cuando no desperdicie la pila) y lo reutiliza. Asignar un bloque gigante en el montón (o su disco duro, si es realmente grande) es bastante más costoso, pero ambos son gastos generales O ( log n ) que palidecen en comparación con el trabajo O ( n ) mencionado anteriormente.$n$$O(\log n)$$O(n)$

Por último, tenga en cuenta que Quicksort es ligeramente sensible a la entrada que está en el orden correcto, en cuyo caso puede omitir algunos intercambios. Mergesort no tiene tales optimizaciones, lo que también hace que Quicksort sea un poco más rápido en comparación con Mergesort.

Use el tipo que se adapte a sus necesidades.

En conclusión: ningún algoritmo de clasificación es siempre óptimo. Elija el que mejor se adapte a sus necesidades. Si necesita un algoritmo que sea el más rápido para la mayoría de los casos, y no le importa, podría terminar siendo un poco lento en casos excepcionales, y no necesita un tipo estable, use Quicksort. De lo contrario, utilice el algoritmo que mejor se adapte a sus necesidades.

En uno de los tutoriales de programación de mi universidad, les pedimos a los estudiantes que compararan el rendimiento de QuickSort, Mergesort, Insertion Sort y Python en el list.sort incorporado (llamado Timsort ). Los resultados experimentales me sorprendieron profundamente ya que el list.sort incorporado funcionó mucho mejor que otros algoritmos de clasificación, incluso con instancias que fácilmente colapsaron rápidamente. Por lo tanto, es prematuro concluir que la implementación habitual de clasificación rápida es la mejor en la práctica. Pero estoy seguro de que hay una implementación mucho mejor de quicksort, o alguna versión híbrida del mismo.

Este es un buen artículo de blog de David R. MacIver que explica Timsort como una forma de combinación adaptativa.

Creo que una de las principales razones por las que QuickSort es tan rápido en comparación con otros algoritmos de clasificación es porque es compatible con la caché. Cuando QS procesa un segmento de una matriz, accede a elementos al principio y al final del segmento, y se mueve hacia el centro del segmento.

Entonces, cuando comienzas, accedes al primer elemento de la matriz y una pieza de memoria ("ubicación") se carga en el caché. Y cuando intentas acceder al segundo elemento, (lo más probable) ya está en el caché, por lo que es muy rápido.

Otros algoritmos como heapsort no funcionan así, saltan mucho en la matriz, lo que los hace más lentos.

Otros ya han dicho que el tiempo de ejecución promedio asintótico de Quicksort es mejor (en la constante) que el de otros algoritmos de clasificación (en ciertas configuraciones).

$\cal{O}(n \log n)$

Tenga en cuenta que hay muchas variantes de Quicksort (véase, por ejemplo, la disertación de Sedgewick). Se desempeñan de manera diferente en diferentes distribuciones de entrada (uniforme, casi ordenada, casi inversamente ordenada, muchos duplicados, ...), y otros algoritmos podrían ser mejores para algunos.

$k \approx 10$

En comparación con otros algoritmos de clasificación basados ​​en comparación con $O(n \lg n)$

ps: para ser precisos, ser mejor que otros algoritmos depende de la tarea. Para algunas tareas, podría ser mejor usar otros algoritmos de clasificación.

Ver también:

• Comparación de clasificación rápida con otros algoritmos de clasificación

• Comparación de heap-sort con otros algoritmos de ordenación

$\Theta(n^2)$$\Theta(n\log n)$

La segunda razón es que realiza la in-placeclasificación y funciona muy bien con entornos de memoria virtual.

ACTUALIZACIÓN:: (Después de los comentarios de Janoma y Svick)

Para ilustrar esto mejor, permítanme dar un ejemplo usando Merge Sort (porque Merge sort es el siguiente algoritmo de ordenación ampliamente adoptado después de la ordenación rápida, creo) y decirles de dónde provienen las constantes adicionales (según mi leal saber y entender por qué creo La ordenación rápida es mejor):

Considere la siguiente secuencia:

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

Si te importa ver cómo está sucediendo la última etapa, el primer 12 se compara con el 8 y el 8 es más pequeño, por lo que va primero. Ahora 12 es OTRA VEZ en comparación con 21 y 12 sigue, y así sucesivamente. Si toma la fusión final, es decir, 4 elementos con otros 4 elementos, incurre en muchas comparaciones EXTRA como constantes que NO se incurre en la Clasificación rápida. Esta es la razón por la cual se prefiere la ordenación rápida.

Mi experiencia trabajando con datos del mundo real es que quicksort es una mala elección . Quicksort funciona bien con datos aleatorios, pero los datos del mundo real a menudo no son aleatorios.

En 2008, rastreé un error de software colgado hasta el uso de quicksort. Un tiempo después escribí implementaciones simples de clasificación de inserción, clasificación rápida, clasificación de montón y clasificación de combinación y las probé. Mi tipo de fusión superó a todos los demás mientras trabajaba en grandes conjuntos de datos.

Desde entonces, la opción de combinación es mi algoritmo de selección preferido. Es elegante Es simple de implementar. Es un tipo estable. No degenera en comportamiento cuadrático como lo hace quicksort. Me cambio a la inserción para ordenar pequeños arreglos.

En muchas ocasiones, me he dado cuenta de que una implementación determinada funciona sorprendentemente bien para la clasificación rápida solo para descubrir que en realidad no es una clasificación rápida. A veces, la implementación cambia entre quicksort y otro algoritmo y, a veces, no usa quicksort en absoluto. Como ejemplo, las funciones qsort () de GLibc en realidad usan la combinación de clasificación. Solo si falla la asignación del espacio de trabajo, vuelve al ordenamiento rápido in situ que un comentario de código llama "el algoritmo más lento" .

Editar: los lenguajes de programación como Java, Python y Perl también usan la combinación de clasificación, o más precisamente una derivada, como Timsort o clasificación de combinación para conjuntos grandes y clasificación de inserción para conjuntos pequeños. (Java también utiliza la clasificación rápida de doble pivote, que es más rápida que la clasificación rápida simple).

1 - La ordenación rápida está en su lugar (no necesita memoria adicional, aparte de una cantidad constante).

2 - La clasificación rápida es más fácil de implementar que otros algoritmos de clasificación eficientes.

3 - La clasificación rápida tiene factores constantes más pequeños en su tiempo de ejecución que otros algoritmos de clasificación eficientes.

Actualización: para la ordenación por fusión, debe realizar algunas "fusiones", que necesitan una matriz adicional para almacenar los datos antes de fusionarse; pero en forma rápida, no lo haces. Es por eso que la clasificación rápida está en su lugar. También hay algunas comparaciones adicionales realizadas para la fusión que aumentan los factores constantes en el orden de fusión.

¿En qué condiciones es un algoritmo de clasificación específico el más rápido?

$\Theta(\log(n)^2)$$\Theta(n \cdot \log(n)^2)$

$\Theta(n \cdot k)$$\Theta(n \cdot m)$$k=2^{\#number\_of\_Possible\_values}$$m = \#maximum\_length\_of\_keys$

3) ¿La estructura de datos subyacente consiste en elementos vinculados? Sí -> siempre utiliza el orden de fusión en el lugar. Hay un tamaño fijo fácil de implementar o de abajo hacia arriba adaptativo (también conocido como natural) que combinan tipos de aridades diferentes para las estructuras de datos vinculadas, y dado que nunca requieren copiar todos los datos en cada paso y tampoco requieren recursiones, son más rápido que cualquier otro tipo de comparación general, incluso más rápido que el tipo rápido.

$\Theta(n)$ memoria adicional en el peor de los casos que consiste en índices originales, que también deben mantenerse sincronizados con cada intercambio que se realizará en los datos de entrada, de modo que cada ganancia de rendimiento que la clasificación rápida pueda tener sobre fusión el tipo probablemente se frustra.

5) ¿Se puede vincular el tamaño de los datos subyacentes a un tamaño pequeño a mediano? por ejemplo, ¿n <10,000 ... 100,000,000 (dependiendo de la arquitectura subyacente y la estructura de datos)? Sí -> utiliza el ordenamiento bitónico o el mezclador impar-par de Batcher. Ir a 1)

$\Theta(n)$$\Theta(n^2)$$\Theta(n \cdot \log(n)^2)$se conocen los peores casos de tiempo de ejecución, o tal vez intente ordenar los peines. No estoy seguro de que la ordenación de concha o la de peine funcionen razonablemente bien en la práctica.

$\Theta(\log(n))$$\Theta(n)$$\Theta(n)$$\Theta(\log(n))$$\Theta(n^2)$$\Theta(n)$$\Theta(n)$$\Theta(\log(n))$$\Theta(n \cdot \log(n))$

$\Theta(n \cdot \log(n))$

Sugerencias de implementación para quicksort:

$\Theta(n)$$\Theta(\log(n))$$\Theta(n^{\log_k(k-1)})$

2) Existen variantes iterativas ascendentes de quicksort, pero AFAIK, tienen los mismos límites de espacio y tiempo asintóticos que los de arriba hacia abajo, con los lados inferiores adicionales de ser difíciles de implementar (por ejemplo, administrar explícitamente una cola). Mi experiencia es que, para fines prácticos, nunca vale la pena considerarlos.

Sugerencias de implementación para mergesort:

1) Mergesort Bottum-Up es siempre más rápido que Mergesort de arriba hacia abajo, ya que no requiere llamadas de recursión.

2) el mergesort muy ingenuo puede acelerarse utilizando un doble buffer y cambiar el buffer en lugar de copiar los datos de la matriz temporal después de cada paso.

3) Para muchos datos del mundo real, mergesort adaptativo es mucho más rápido que un mergesort de tamaño fijo.

$\Theta(k)$$\Theta(\log(k))$$\Theta(1)$$\Theta(n)$

Por lo que he escrito, está claro que la clasificación rápida a menudo no es el algoritmo más rápido, excepto cuando se aplican las siguientes condiciones:

1) hay más de unos "pocos" valores posibles

2) la estructura de datos subyacente no está vinculada

3) no necesitamos un pedido estable

4) los datos son lo suficientemente grandes como para que el ligero tiempo de ejecución asintótico subóptimo de un clasificador bitónico o un mezclador impar-par de Batcher se active

5) los datos no están casi ordenados y no consisten en partes más grandes ya ordenadas

6) podemos acceder a la secuencia de datos simultáneamente desde múltiples lugares

$\Theta(\log(n))$$\Theta(n)$

PD: Alguien debe ayudarme con el formato del texto.

La mayoría de los métodos de ordenación tienen que mover datos en pasos cortos (por ejemplo, la ordenación por fusión realiza cambios localmente, luego fusiona este pequeño dato y luego fusiona uno más grande ...). En consecuencia, necesita muchos movimientos de datos si los datos están lejos de su destino.

$a \le b$