Algoritmo de ordenamiento
En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.
Estabilidad
Los algoritmos de ordenamiento estable mantienen un relativo preorden total. Esto significa que un algoritmo es estable solo cuando hay dos registros R y S con la misma clave y con R apareciendo antes que S en la lista original.
Cuando elementos iguales (indistinguibles entre sí), como números enteros, o más generalmente, cualquier tipo de dato en donde el elemento entero es la clave, la estabilidad no es un problema. De todas formas, se asume que los siguientes pares de números están por ser ordenados por su primer componente:
(4, 1) (3, 7) (3, 1) (5, 6)
En este caso, dos resultados diferentes son posibles, uno de los cuales mantiene un orden relativo de registros con claves iguales, y una en la que no:
(3, 7) (3, 1) (4, 1) (5, 6) (orden mantenido) (3, 1) (3, 7) (4, 1) (5, 6) (orden cambiado)
Los algoritmos de ordenamiento inestable pueden cambiar el orden relativo de registros con claves iguales, pero los algoritmos estables nunca lo hacen. Los algoritmos inestables pueden ser implementados especialmente para ser estables. Una forma de hacerlo es extender artificialmente el cotejamiento de claves, para que las comparaciones entre dos objetos con claves iguales sean decididas usando el orden de las entradas original. Recordar este orden entre dos objetos con claves iguales es una solución poco práctica, ya que generalmente acarrea tener almacenamiento adicional.
Ordenar según una clave primaria, secundaria, terciara, etc., puede ser realizado utilizando cualquier método de ordenamiento, tomando todas las claves en consideración (en otras palabras, usando una sola clave compuesta). Si un método de ordenamiento es estable, es posible ordenar múltiples ítems, cada vez con una clave distinta. En este caso, las claves necesitan estar aplicadas en orden de aumentar la prioridad.
Ejemplo: ordenar pares de números, usando ambos valores
(4, 1) (3, 7) (3, 1) (4, 6) (original)
(4, 1) (3, 1) (4, 6) (3, 7) (después de ser ordenado por el segundo valor) (3, 1) (3, 7) (4, 1) (4, 6) (después de ser ordenado por el primer valor)
Por otro lado:
(3, 7) (3, 1) (4, 1) (4, 6) (después de ser ordenado por el primer valor)
(3, 1) (4, 1) (4, 6) (3, 7) (después de ser ordenando por el segundo valor,
el orden por el primer valor es perturbado)
Lista de algoritmos de ordenamiento
Algunos algoritmos de ordenamiento agrupados según estabilidad tomando en cuenta la complejidad computacional.
| Estables | ||||
| Nombre traducido | Nombre original | Complejidad | Memoria | Método |
| Ordenamiento de burbuja | Bubblesort | O(n²) | O(1) | Intercambio |
| Ordenamiento de burbuja bidireccional | Cocktail sort | O(n²) | O(1) | Intercambio |
| Ordenamiento por inserción | Insertion sort | O(n²)("(en el peor de los casos)") | O(1) | Inserción |
| Ordenamiento por casilleros | Bucket sort | O(n) | O(n) | No comparativo |
| Ordenamiento por cuentas | Counting sort | O(n+k) | O(n+k) | No comparativo |
| Ordenamiento por mezcla | Merge sort | O(n log n) | O(n) | Mezcla |
| Ordenamiento con árbol binario | Binary tree sort | O(n log n) | O(n) | Inserción |
| Pigeonhole sort | O(n+k) | O(k) | ||
| Ordenamiento Radix | Radix sort | O(nk) | O(n) | No comparativo |
| Distribution sort | O(n³) versión recursiva | O(n²) | ||
| Gnome sort | O(n²) | O(1) | ||
| Inestables | ||||
| Nombre traducido | Nombre original | Complejidad | Memoria | Método |
| Ordenamiento Shell | Shell sort | O(n1.25) | O(1) | Inserción |
| Comb sort | O(n log n) | O(1) | Intercambio | |
| Ordenamiento por selección | Selection sort | O(n²) | O(1) | Selección |
| Ordenamiento por montículos | Heapsort | O(n log n) | O(1) | Selección |
| Smoothsort | O(n log n) | O(1) | Selección | |
| Ordenamiento rápido | Quicksort | Promedio: O(n log n), peor caso: O(n²) | O(log n) | Partición |
| Several Unique Sort | Promedio: O(n u), peor caso: O(n²); u=n; u = número único de registros | |||
| Cuestionables, imprácticos | ||||
| Nombre traducido | Nombre original | Complejidad | Memoria | Método |
| Bogosort | O(n × n!), peor: no termina | |||
| Pancake sorting | O(n), excepto en máquinas de Von Neumann | |||
| Ordenamiento Aleatorio | Randomsort | Promedio: O(n!) Peor: No termina | ||
