¿Cuáles son los casos de uso cuando se prefiere un algoritmo de clasificación particular sobre otros - merge sort frente a quick sort frente a heap sort frente a intro sort, etc.?
¿Cuándo se usa cada algoritmo de clasificación?
¿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?
Un conjunto de animaciones para diferentes tipos de datos y algoritmos se pueden encontrar en sorting-algorithms.com
Ok +1 porque eso es genial. – GrayWizardx
Esto no responde la pregunta. –
OK, quizás sí. –
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
Lo que los enlaces proporcionados a comparaciones/animaciones no consideran es cuando la cantidad de datos excede la memoria disponible --- momento en el que el número de pasadas a través de los datos, es decir, I/O-costes, dominar 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.
Quicksort suele ser el más rápido en promedio, pero tiene algunas conductas bastante desagradables en el peor de los casos. Entonces, si tiene que garantizar que no hay datos incorrectos, O(N^2), debe evitarlo.
Merge-sort utiliza memoria extra, pero es especialmente adecuada para la clasificación externa (es decir, archivos de gran tamaño que no caben en la memoria).
Tipo de montículo puede ordenar en el lugar y no tiene el peor comportamiento cuadrático de caso, pero en promedio es más lento que el método rápido en la mayoría de los casos.
Cuando solo se trata de 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 oferta rápida.
+1: Para "En el 99% de los casos, estarás bien con los tipos de biblioteca, que generalmente se basan en quicksort". –
El pivoteo aleatorizado proporciona a Quicksort un tiempo de ejecución de O (nlogn) para todos los propósitos prácticos, sin necesidad de garantías sobre datos incorrectos. Realmente no creo que nadie implemente un quicksort O (n^2) para ningún código de producción. – MAK
MAK, excepto, por ejemplo, la biblioteca estándar C qsort? (http://www.google.com/codesearch/p?hl=en&sa=N&cd=6&ct=rc#XAzRy8oK4zA/libc/stdlib/qsort.c&q=memmove%20android%20package:%22git://android.git. kernel.org/platform/bionic.git%22&d=1) - en el que la mayoría de los "códigos de producción" dependen de –
En primer lugar, una definición, ya que es bastante importante: una clasificación estable es una que garantiza que no se volverá a ordenar elementos con claves idénticas.
recomendaciones:
ordenar rápida: Cuando no se necesita una especie estable y un rendimiento promedio caso importa más que peor desempeño caso. 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.
Combinar tipo: Cuando necesite un tipo 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ículo: Cuando no necesita un tipo estable y se preocupa más por el peor de los casos, el rendimiento medio de la carcasa. 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.
Tipo de inserción: Cuando N se garantiza que es pequeño, incluso como el caso base de un tipo de ordenación rápida o combinación. Si bien es O (N^2), tiene una constante muy pequeña y es un tipo estable.
Tipo de burbuja, selección tipo: cuando está haciendo algo rápido y sucio y por alguna razón no puede 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.
tipo no de comparación: En algunas condiciones bastante limitado Es posible romper el O (N log N) de barrera y especie en O (N). Aquí hay algunos casos en los que vale la pena intentarlo:
Clasificación de conteo: Al ordenar enteros con un rango limitado.
Ordenamiento de radios: Cuando log (N) es significativamente mayor que K, donde K es el número de radix dígitos.
Clasificación de cubo: Cuando puede garantizar que su entrada se distribuye de manera aproximadamente uniforme.
Como recuerdo, el tipo de almacenamiento dinámico también tiene un tiempo de ejecución muy predecible ya que hay poca variación entre diferentes entradas del mismo tamaño, pero eso es de menos interés que su límite de espacio constante. También encuentro que la ordenación por inserción es la más fácil de implementar de los tipos n^2, pero tal vez sea solo yo. Por último, es posible que también desee mencionar Shell sort, que es casi tan simple de implementar como la ordenación de inserción, pero tiene un mejor rendimiento, aunque todavía no n log n. – JaakkoK
¡No olvide [Bogosort] (http://en.wikipedia.org/wiki/Bogosort)! ;-) –
+1 Muy interesante. ¿Le importaría explicar cómo puede "garantizar ... distribución aproximadamente uniforme"? para el tipo de cubo? –
@dsimcha escribió: Conteo para ordenar: Cuando está ordenando números enteros con una gama limitada
que cambiaría a que:
Conteo especie: Cuando los números enteros positivos (tipo 0 - Entero. 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 adicional 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;
(a pesar de que en realidad le permitirá a MAX_VALUE-2) véase: Do Java arrays have a maximum size?
También me explicaría que la complejidad Radix sort es O (wn) para n claves que son números enteros de 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). (de wikipedia)
Una guía como http://bigocheatsheet.com/ para este material sería greaaaat –