Algoritmo de ordenamiento
De Wikipedia, la enciclopedia libre
En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista siguiendo el orden dado por una relación de orden. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. El ordenamiento eficiente es importante para optimizar el uso de otros algoritmos (como los de búsqueda y merge) que requieren listas ordenadas para funcionar correctamente. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos. Más formalmente, la salida debe satisfacer las siguientes dos condiciones:
- La salida está en orden no decremental (todo elemento es no menor que el elemento anterior de acuerdo al orden total deseado).;
- La salida es una permutación, o reordenamiento, de la entrada.
Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su simple y familiar planteo. Por ejemplo, Bubble Sort fue analizado tan temprano como 1956.[1] Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son prevalentes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema provee una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, Algoritmos Divide y vencerás, Estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.
[editar] Clasificación
Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:
- La más común es clasificar según el lugar donde se realice la ordenación
- Algoritmos de ordenamiento interno: en la memoria del ordenador.
- Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
- Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
- Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.
- Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.
- Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha la reordenamos en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha. Otro caso sería cuando no interesan las mayúsculas y minúsculas, pero se quiere que si una clave aBC estaba antes que AbC, en el resultado ambas claves aparezcan juntas y en el orden original: aBC, AbC.
- Cuando los elementos son indistinguibles (porque cada elemento se ordena por la clave completa) la estabilidad no interesa. Los algoritmos de ordenamiento que no son estables se pueden implementar de modo de que lo sean. Una manera de hacer esto es modificar artificialmente la clave de ordenamiento de modo que la posición original en la lista participe del ordenamiento en caso de coincidencia.
Los algoritmos se distinguen por las siguientes características:
- complejidad computacional (peor caso, caso promedio y mejor caso) en términos de n, el tamaño de la lista o arreglo. Para esto se usa el concepto de orden de una función y se usa la notación O(n). El mejor comportamiento para ordenar (si no se aprovecha la estructura de las claves) es O(n log n). Los algoritmos más simples son cuadráticos, es decir O(n²). Los algoritmos que aprovechan la estructura de las claves de ordenamiento (p. ej. bucket sort) pueden ordenar en O(kn) donde k es el tamaño del espacio de claves. Como dicho tamaño es conocido a priori, se puede decir que estos algoritmos tienen un desempeño lineal, es decir O(n).
- uso de memoria y otros recursos computacionales. También se usa la notación O(n).
Algunos algoritmos de ordenamiento agrupados según estabilidad tomando en cuenta la complejidad computacional.
| Estables | ||
| Nombre | Complejidad | Memoria adicional |
| Ordenamiento de burbuja (Bubblesort) | O(n²) | |
| Burbuja bidireccional (Cocktail sort) | O(n²) | |
| Ordenamiento por inserción (Insertion sort) | O(n²) | |
| Ordenamiento por casilleros (Bucket sort) | O(n) | O(n) |
| Counting sort | O(n+k) | O(n+k) |
| Merge sort | O(n log n) | |
| Árbol binario (Binary tree sort) | O(n log n) | O(n) |
| Pigeonhole sort | O(n+k) | O(k) |
| Radix sort | O(nk) | O(n) |
| Stupid sort | O(n³) versión recursiva | O(n²) |
| Gnome sort | O(n²) | |
| Inestables | ||
| Nombre | Complejidad | Memoria adicional |
| Shell sort | O(n1.25) | |
| Comb sort | O(n log n) | |
| Selection sort | O(n²) | |
| Heapsort | O(n log n) | |
| Smoothsort | O(n log n) | |
| Ordenamiento rápido (Quicksort) | Promedio: O(n log n), peor caso: O(n²) |
|
| Several Unique Sort | Promedio: O(n u), peor caso: O(n²); u=n; u = número único de registros |
|
| Cuestionables, imprácticos | ||
| Nombre | Complejidad | Memoria adicional |
| Bogosort | O(n × n!), peor: no termina | |
| Pancake sorting | O(n), excepto en máquinas de Von Neumann |
|
| Randomsort | ||
