Algoritmos de ordenamiento
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. Ordenar eficientemente es
importante para posteriormente usar en forma otros algoritmos como los de búsqueda, merge (por ej., para comparación de
listas), dado que para aplicar ciertos algoritmos es necesario que previamente los elementos se encuentren ordenados. También es
útil para poner datos en forma canónica y para generar resultados legibles por humanos.
Clasificación
Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:
- complejidad computacional (peor caso, caso
promedio y mejor caso) en términos de n, el tamaño de la lista. 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(n log
k) 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).
- 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.
Algunos algoritmos de ordenamiento agrupados según estabilidad tomando en cuenta la complejidad computacional.
Estables
- Orden de burbuja (Bubblesort) - O(n²)
- Cocktail sort (burbuja
bidireccional) - O(n²)
- Orden por inserción (Insertion sort) - O(n²)
- Bucket sort (orden
mediante casilleros) - O(n); requiere
O(n) de memoria extra
- Counting sort - O(n+k); requiere
O(n+k) de memoria extra
- Merge sort - O(n log n)
- Árbol binario (Binary
tree sort) - O(n log
n); requiere O(n) de memoria extra
- Pigeonhole sort -
O(n+k); requiere
O(k) de memoria extra
- Radix sort - O(nk); requiere O(n) de memoria extra
- Stupid sort - O(n³); versión recursiva, requiere
O(n²) de memoria extra-
- Gnome sort - O(n²)
Inestables
- 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)
- Quicksort (orden rápido) - tiempo esperado O(n log n), O(n²) en el
peor de los casos
- Several Unique
Sort - tiempo esperado O(n u),
O(n²) en el peor de los casos, donde u=n y u es el número único de registros
Algoritmos cuestionables:
- Bogosort - tiempo esperado O(n × n!). Peor caso: no
termina.
- Pancake sorting -
O(n), pero no en máquinas de Von Neumann.
- Randomsort
Portada
Favoritos