5.6. Ordenamiento¶
Ordenar es el proceso de ubicar elementos de una colección en algún orden. Por ejemplo, una lista de palabras podría ordenarse alfabéticamente o por longitud. Una lista de ciudades podría ordenarse por población, por área o por código postal. Ya hemos visto una serie de algoritmos que fueron capaces de beneficiarse de tener una lista ordenada (recuerde el ejemplo final del anagrama y la búsqueda binaria).
Se han desarrollado y analizado muchísimos algoritmos de ordenamiento. Esto sugiere que el ordenamiento es una importante área de estudio en las ciencias de la computación. Ordenar un gran número de ítems puede requerir una cantidad considerable de recursos informáticos. Al igual que la búsqueda, la eficiencia de un algoritmo de ordenamiento está relacionada con el número de ítems que se están procesando. Para las pequeñas colecciones, un método de ordenamiento complejo puede resultar más problemático que beneficioso. La sobrecarga puede ser demasiado alta. Por otra parte, para colecciones más grandes, queremos aprovechar tantas mejoras como sean posibles. En esta sección discutiremos varias técnicas de ordenamiento y las compararemos respecto a sus tiempos de ejecución.
Antes de considerar algoritmos específicos, debemos pensar en las operaciones que se pueden utilizar para analizar un proceso de ordenamiento. Primero, será necesario comparar dos valores para ver cuál es más pequeño (o más grande). Para ordenar una colección, será necesario contar con una manera sistemática de comparar los valores para ver si no están en orden. El número total de comparaciones será la forma más común de medir un procedimiento de ordenamiento. En segundo lugar, cuando los valores no están en la posición correcta con respecto a los otros, puede ser necesario intercambiarlos. Este intercambio es una operación costosa y el número total de intercambios también será importante para evaluar la eficiencia global del algoritmo.