¿Por qué es quicksort mejor que otros algoritmos de clasificación en la práctica?

^{Este es un reenvío de una pregunta sobre cs.SE de Janoma . Créditos completos y botín para él o cs.SE.}

En un curso de algoritmos estándar se nos enseña que quicksort es O (n log n) en promedio y O (n²) en el peor de los casos. Al mismo tiempo, se estudian otros algoritmos de clasificación que son O (n log n) 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.

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).

No estaría de acuerdo con que quicksort sea mejor que otros algoritmos de clasificación en la práctica.

Para la mayoría de los propósitos, Timsort : el híbrido entre clasificación de fusión / inserción que explota el hecho de que los datos que clasifica a menudo comienzan casi ordenados o ordenados de forma inversa.

El ordenamiento rápido más simple (sin pivote aleatorio) trata este caso potencialmente común como O (N ^ 2) (reduciéndose a O (N lg N) con pivotes aleatorios), mientras que TimSort puede manejar estos casos en O (N).

De acuerdo con estos puntos de referencia en C # que comparan el incorporado en la clasificación rápida a TimSort, Timsort es significativamente más rápido en los casos en su mayoría ordenados, y ligeramente más rápido en el caso de datos al azar y TimSort consigue mejor si la función de comparación es particularmente lento. No he repetido estos puntos de referencia y no me sorprendería si quicksort supera ligeramente a TimSort por alguna combinación de datos aleatorios o si hay algo peculiar en el ordenamiento integrado de C # (basado en quicksort) que lo está ralentizando. Sin embargo, TimSort tiene distintas ventajas cuando los datos pueden clasificarse parcialmente, y es aproximadamente igual a la clasificación rápida en términos de velocidad cuando los datos no se clasifican parcialmente.

TimSort también tiene una ventaja adicional de ser un tipo estable, a diferencia de quicksort. La única desventaja de TimSort utiliza la memoria O (N) versus O (lg N) en la implementación habitual (rápida).

La ordenación rápida se considera más rápida porque el coeficiente es más pequeño que cualquier otro algoritmo conocido. No hay razón o prueba para eso, simplemente no se ha encontrado un algoritmo con un coeficiente más pequeño. Es cierto que otros algoritmos también tienen tiempo O ( n log n ), pero en el mundo real el coeficiente también es importante.

Tenga en cuenta que para la inserción de datos pequeños, el tipo (el que se considera O ( n ² )) es más rápido debido a la naturaleza de las funciones matemáticas. Esto depende de los coeficientes específicos que varían de una máquina a otra. (Al final, solo se está ejecutando realmente el ensamblaje). Entonces, a veces, un híbrido de clasificación rápida e inserción es lo más rápido en la práctica, creo.

Quicksort no supera a todos los demás algoritmos de ordenación. Por ejemplo, la ordenación del montón de abajo hacia arriba ( Wegener 2002 ) supera a la clasificación rápida para cantidades razonables de datos y también es un algoritmo en el lugar. También es fácil de implementar (al menos, no más difícil que alguna variante optimizada de clasificación rápida).

Simplemente no es tan conocido y no lo encuentras en muchos libros de texto, eso puede explicar por qué no es tan popular como Quicksort.

No debe centrarse solo en el peor de los casos y solo en la complejidad del tiempo. Se trata más del promedio que de lo peor, y se trata del tiempo y el espacio.

Ordenación rápida:

• tiene una complejidad de tiempo promedio de Θ ( n log n );
• se puede implementar con la complejidad espacial de Θ (log n );

También tenga en cuenta que la notación O grande no tiene en cuenta ninguna constante, pero en la práctica sí hace la diferencia si el algoritmo es varias veces más rápido. Θ ( n log n ) significa que ese algoritmo se ejecuta en K  n  log ( n ), donde K es constante. Quicksort es el algoritmo de clasificación de comparación con la K más baja .

Quicksort suele ser una buena opción, ya que es razonablemente rápido y razonablemente rápido y fácil de implementar.

Si te tomas en serio la clasificación de grandes cantidades de datos muy rápidamente, entonces probablemente estés mejor con alguna variación en MergeSort. Esto puede hacerse para aprovechar el almacenamiento externo, puede hacer uso de múltiples hilos o incluso procesos, pero no son triviales para el código.

El rendimiento real de los algoritmos depende de la plataforma, así como del lenguaje, el compilador, la atención del programador a los detalles de implementación, el esfuerzo de optimización específico, etc. Por lo tanto, la "ventaja de factor constante" de quicksort no está muy bien definida: es un juicio subjetivo basado en las herramientas disponibles actualmente y una estimación aproximada del "esfuerzo de implementación equivalente" por parte de quien realmente realiza el estudio comparativo de rendimiento. .

Dicho esto, creo que quicksort funciona bien (para entrada aleatoria) porque es simple y porque su estructura recursiva es relativamente amigable con la caché. Por otro lado, debido a que su peor caso es fácil de desencadenar, cualquier uso práctico de una clasificación rápida tendrá que ser más complejo de lo que su descripción del libro de texto indicaría: por lo tanto, versiones modificadas como introsort.

Con el tiempo, a medida que cambia la plataforma dominante, diferentes algoritmos pueden ganar o perder su ventaja relativa (mal definida). La sabiduría convencional sobre el rendimiento relativo puede retrasarse con respecto a este cambio, por lo que si no está seguro de qué algoritmo es mejor para su aplicación, debe implementar ambos y probarlos.