Comparación de algoritmos de ordenación

Los algoritmos de ordenación son una parte importante de la gestión de datos. AtCprogramming.com, ofrecemos tutoriales para comprender las técnicas más importantes y de acompañamiento. Cada algoritmo tiene fortalezas y debilidades particulares y, en muchos casos, lo mejor que puede hacer es usar la función de inserción incorporada qsort. Para los momentos en que esto no es una opción o solo necesita un algoritmo de clasificación rápido y sucio, hay una variedad de opciones.

La mayoría de los algoritmos de ordenación funcionan comparando los datos que se ordenan. En algunos casos, puede ser deseable ordenar una gran parte de los datos (por ejemplo, una estructura que contenga un nombre y una dirección) basándose solo en una parte de esos datos.La pieza de datos realmente utilizada para determinar el orden ordenado se llama clave.Los algoritmos de ordenación suelen juzgarse por su eficiencia. En este caso,la eficiencia se refiere a la eficiencia algorítmica como el tamaño de la entrada growslarge y generalmente se basa en el número de elementos a clasificar. La mayoría de los algoritmos en uso tienen una eficiencia algorítmica de O (n^2) orO (n * log (n)). Algunos algoritmos de casos especiales (un ejemplo se menciona en Perlas de programación) pueden ordenar ciertos conjuntos de datos más rápido que O(n*log(n)). Estos algoritmos de registro no se basan en la comparación de los elementos que se ordenan y se basan en pruebas. Se ha demostrado que ningún algoritmo de comparación de claves puede funcionar mejor que O (n * log (n)).
Muchos algoritmos que tienen la misma eficiencia no tienen la misma velocidad en la misma entrada. En primer lugar,los algoritmos deben juzgarse en función de su eficiencia media, en el mejor de los casos y en el peor de los casos. Algunos algoritmos,como quick sort, funcionan excepcionalmente bien para algunas entradas, pero horriblemente para otras. Otros algoritmos, como la ordenación combinada, no se ven afectados por el orden de los datos de entrada.Incluso una versión modificada de bubble sort puede terminar en O (n) para las entradas más favorables.
Un segundo factor es el «término constante». Como la notación big-O abstrae muchos de los detalles de un proceso, es bastante útil para observar la imagen grande. Pero una cosa que se elimina es la constante frente a la expresión: por ejemplo, O(c * n) es solo O(n). En el mundo real, la constante, c, variará según los diferentes algoritmos. Un cortocircuito bien implementado debe tener un multiplicador constante mucho más pequeño que el de clasificación en pilas.
Un segundo criterio para juzgar a los algoritmos es su requerimiento de espacio do ¿requieren espacio en scratch o se puede ordenar la matriz en su lugar (sin memoria adicional más allá de unas pocas variables)? Algunos algoritmos nunca requieren espacio extra, mientras que otros son más fáciles de entender cuando se implementan con espacio extra (por ejemplo, la ordenación de montones se puede hacer en su lugar, pero conceptualmente es mucho más fácil pensar en un montón separado). Los requisitos de espacio pueden incluso depender de la estructura de datos utilizada (ordenar por fusión en matrices versus ordenar por fusión en listas enlazadas, por ejemplo).
Un tercer criterio es la estabilidad preserve ¿el orden conserva el orden de las claves con valores iguales? La mayoría de los tipos simples hacen precisamente esto, pero algunos tipos, como los de basura, no lo hacen.
El siguiente gráfico compara los algoritmos de ordenación en los diversos criterios mencionados anteriormente; los algoritmos con términos constantes más altos aparecen primero, aunque este es claramente un concepto dependiente de la implementación y solo debe tomarse como una guía aproximada al elegir entre tipos de la misma eficiencia de big-O.

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Constante	Estable	aunque sea perfectamente ordenados de entrada requiere la digitalización de toda la matriz
Ordenación por Inserción	O(n^2)	O(n)	O(n^2)	Constante	Estable	En el mejor de los casos (ya clasificado), cada inserto requiere la constante de tiempo de
Heap Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Constante	Inestable	mediante el uso de matriz de entrada como de almacenamiento para el montón, es posible lograr un espacio continuo
Merge Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Depende	Estable	En las matrices, de combinación de tipo requiere O(n) en el espacio; en las listas enlazadas, combinación de tipo requiere de un espacio
Quicksort	O(n*log(n))	O(n*log(n))	O(n^2)	Constante	Estable	escoger al Azar un valor dinámico (o transposición de la matriz antes de la selección) puede ayudar a evitar el peor de los escenarios tales como perfectamente ordenado la matriz.