algorithm - complexity - ¿Cuándo se usa cada algoritmo de clasificación?

sorting algorithms complexity

Question

¿Cuáles son los casos de uso cuando se prefiere un algoritmo de clasificación particular sobre otros - merge sort vs quick sort vs heap sort vs intro sort , etc.?

¿Existe una guía recomendada para usarlos según el tamaño, el tipo de estructura de datos, la memoria disponible y la memoria caché, y el rendimiento de la CPU?

Answer 1

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

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

Answer 2

Lo que los enlaces proporcionados a las comparaciones / animaciones no consideran es cuando la cantidad de datos excede la memoria disponible --- en cuyo punto el número de pasadas sobre los datos, es decir, los costos de E / S, dominan el tiempo de ejecución. Si necesita hacer eso, lea en "clasificación externa" que generalmente cubre variantes de tipo fusió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 geniales que comparan varios algoritmos de clasificación.

Answer 3

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

Recomendaciones:

Clasificación rápida: cuando no se necesita una clasificación estable y el rendimiento medio de un caso es más importante que el peor de los casos. Una clasificació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 recursión.

Tipo de combinación: cuando necesita una clasificación estable, O (N log N), esta es su única opción. Las únicas desventajas son que usa O (N) espacio auxiliar y tiene una constante ligeramente mayor que una clasificación rápida. Hay algunos géneros de fusión en el lugar, pero AFAIK no son estables o son peores que O (N log N). Incluso los géneros O (N log N) en el lugar tienen una constante mucho más grande que el tipo de fusión simple que son más curiosidades teóricas que algoritmos útiles.

Tipo de montón: cuando no necesita un tipo estable y le preocupa más el peor rendimiento de caso que el rendimiento medio de un caso. Está garantizado que es O (N log N) y utiliza O (1) espacio auxiliar, lo que significa que no se agotará inesperadamente ni acumulará espacio en entradas muy grandes.

Introsort: Este es un tipo rápido 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 ordenación simple y rápida, ya que obtiene 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 mucha memoria limitada 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, incluido como caso base de ordenación rápida o fusión. Si bien es O (N ^ 2), tiene una constante muy pequeña y es un tipo estable.

Tipo de burbuja, ordenación por 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 la ordenación por inserción es que es un poco más fácil de implementar.

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

Clasificación de conteo: cuando ordena números enteros con un rango limitado.

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

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

Answer 4

Un conjunto de animaciones para diferentes tipos de datos y algoritmos se puede encontrar en sorting-algorithms.com

Answer 5

@dsimcha escribió: Clasificación de conteo: cuando se ordenan enteros con un rango limitado

Yo cambiaría eso a:

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

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

/**
* 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 de Java tienen un tamaño máximo?

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

Answer 6

Quicksort suele ser el más rápido en promedio, pero tiene algunos comportamientos bastante desagradables en el peor de los casos. Entonces, si tienes que garantizar que ningún dato malo te da O(N^2) , debes evitarlo.

Merge-sort utiliza memoria extra, pero es particularmente adecuada para la clasificación externa (es decir, archivos de gran tamaño 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 quicksort en la mayoría de los casos.

Donde 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 géneros de la biblioteca, que generalmente se basan en la oferta rápida.