¿Cuándo se usa cada algoritmo de clasificación? [cerrado]

¿Cuáles son los casos de uso cuando se prefiere un algoritmo de ordenación en particular sobre otros: fusionar ordenación vs QuickSort vs heapsort vs 'intro sort', etc.?

¿Existe una guía recomendada para usarlos en función del tamaño, tipo de estructura de datos, memoria y caché disponibles y rendimiento de la CPU?

Primero, una definición, ya que es bastante importante: una ordenación estable es aquella que garantiza no reordenar elementos con claves idénticas.

Recomendaciones:

Clasificación rápida: cuando no necesita una clasificación estable y el rendimiento promedio del caso es más importante que el peor de los casos. Una ordenación rápida es O (N log N) en promedio, O (N ^ 2) en el peor de los casos. Una buena implementación utiliza el almacenamiento auxiliar O (log N) en forma de espacio de pila para la recursividad.

Ordenar por fusión: cuando necesita una ordenación estable, O (N log N), esta es su única opción. El único inconveniente es que usa espacio auxiliar O (N) y tiene una constante ligeramente mayor que una clasificación rápida. Hay algunos tipos de fusión en el lugar, pero AFAIK no son todos estables o peor que O (N log N). Incluso los tipos O (N log N) en el lugar tienen una constante mucho mayor que el tipo de fusión simple que son más curiosidades teóricas que algoritmos útiles.

Clasificación de almacenamiento dinámico: cuando no necesita una ordenación estable y le importa más el rendimiento del peor de los casos que el rendimiento promedio del caso. Se garantiza que sea O (N log N), y utiliza O (1) espacio auxiliar, lo que significa que no se quedará sin espacio de pila o montón de forma inesperada en entradas muy grandes.

Introsort: esta es una ordenación rápida que cambia a una ordenación de montón después de una cierta profundidad de recursión para evitar el peor caso de O (N ^ 2) de ordenación rápida. Casi siempre es mejor que una clasificación rápida simple, ya que obtienes el caso promedio de una clasificación rápida, con un rendimiento garantizado de O (N log N). Probablemente, la única razón para usar una ordenación de montón en lugar de esto es en sistemas con limitaciones severas de memoria donde el espacio de pila O (log N) es prácticamente significativo.

Clasificación de inserción : cuando se garantiza que N es pequeño, incluso como el caso base de una clasificación rápida o una combinación. Si bien esto es O (N ^ 2), tiene una constante muy pequeña y es un tipo estable.

Clasificación de burbujas, clasificación de selección : cuando estás haciendo algo rápido y sucio y, por alguna razón, no puedes usar el algoritmo de clasificación de la biblioteca estándar. La única ventaja que tienen sobre el tipo de inserción es que es un poco más fácil de implementar.

Clases de no comparación: en algunas condiciones bastante limitadas, es posible romper la barrera O (N log N) y clasificar en O (N). Aquí hay algunos casos en los que vale la pena intentarlo:

Conteo ordenado: cuando está ordenando enteros con un rango limitado.

Clasificación de radix: cuando log (N) es significativamente mayor que K, donde K es el número de dígitos de radix.

Clasificación de cubetas: cuando puede garantizar que su entrada se distribuye aproximadamente de manera uniforme.

Quicksort suele ser el más rápido en promedio, pero tiene algunos comportamientos bastante desagradables en el peor de los casos. Entonces, si tiene que garantizar que no le brinden datos incorrectos O(N^2), debe evitarlo.

Merge-sort utiliza memoria adicional, pero es particularmente adecuado para la ordenación externa (es decir, archivos enormes que no caben en la memoria).

Heap-sort puede ordenar en el lugar y no tiene el peor comportamiento cuadrático, pero en promedio es más lento que el de clasificación rápida en la mayoría de los casos.

Cuando solo están involucrados enteros en un rango restringido, puede usar algún tipo de clasificación de radix para hacerlo muy rápido.

En el 99% de los casos, estará bien con los tipos de biblioteca, que generalmente se basan en la clasificación rápida.

La página de Wikipedia sobre algoritmos de clasificación tiene una excelente tabla de comparación.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Lo que los enlaces proporcionados a las comparaciones / animaciones no consideran es cuando la cantidad de datos excede la memoria disponible, momento en el cual el número de pases sobre los datos, es decir, los costos de E / S, dominan el tiempo de ejecución. Si necesita hacer eso, lea sobre "clasificación externa" que generalmente cubre variantes de tipos de combinación y montón.

http://corte.si/posts/code/visualisingsorting/index.html y http://corte.si/posts/code/timsort/index.html también tienen algunas imágenes interesantes que comparan varios algoritmos de clasificación.

@dsimcha escribió: Conteo ordenado: cuando está ordenando enteros con un rango limitado

Cambiaría eso a:

Orden de conteo: cuando ordena enteros positivos (0 - Integer.MAX_VALUE-2 debido al casillero).

Siempre puede obtener los valores máximo y mínimo como una heurística de eficiencia en tiempo lineal también.
También necesita al menos n espacio adicional para la matriz intermedia y obviamente es estable.

/**
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

(aunque en realidad permitirá MAX_VALUE-2) ver: ¿Las matrices Java tienen un tamaño máximo?

También explicaría que la complejidad de clasificación de radix es O (wn) para n claves que son enteros de tamaño de palabra w. A veces, w se presenta como una constante, lo que haría que la ordenación por radix fuera mejor (para un n suficientemente grande) que los mejores algoritmos de ordenación basados ​​en la comparación, que realizan comparaciones O (n log n) para ordenar n claves. Sin embargo, en general, w no puede considerarse una constante: si todas las claves n son distintas, entonces w debe ser al menos log n para que una máquina de acceso aleatorio pueda almacenarlas en la memoria, lo que da como máximo una complejidad de tiempo O (n log n). (de wikipedia)