La importancia de la ordenación.
A parte de su interés practico evidente (ordenar datos rápido), un algoritmo “óptimo” supone un gran reto.
Este es mucho mayor cuando se han desarrollado métodos desde hace decenas de años. Algunos son muy buenos, pero ninguno es óptimo en función de unos parámetros deseables. Por ejemplo, mi objetivo para el II CUSL es hallar un algoritmo de ordenación por comparación, óptimo en el número de comparaciones. Es decir un algoritmo que ordene N datos, utilizando únicamente la operación “<=” (y en consecuencia “<”, la misma operación negada), y que realice el número mínimo necesario de estas comparaciones entre dos elementos, para garantizar que los n elementos estan ordenados.Resumiendo, si alcanzo mi objetivo, para N elementos cualesquiera, el numero de comparaciones estarán entre N-1 (si todos los elementos estan ordenados) y log2(n!) (en el peor caso, ningún tipo de orden aprovechable), con una suave transición entre los dos limites. Además, también me gustaría (y creo firmemente que es posible) que el algoritmo resultante sea sencillo y con un tiempo de ejecución del orden de O(n log n). Como ilustración el algoritmo más rápido de media, conocido es Quicksort, de C.A.R. Hoare, sólo es óptimo en el número de comparaciones para el caso de elementos completamente desordenados, en el caso medio nunca son óptimas, y en el caso de N elementos ordenados son de N-1+N-2+….+1. Es decir hace entre O(n lo n) comparaciones y O(n^2) comparaciones.El problema de la ordenación parece sin embargo simple; de una entrada de N datos desordenados, proporcionar esos mismos N datos ordenados tal que D1<=D2….Dn-1<=Dn. Surgen varias dudas: ¿Porque no es facil resolverlo de forma óptima? Y mejor aún:¿Si encontramos una forma simple de resolverlo de forma óptima, podrá aplicarse esta para la resolución óptima de otros problemas más complejos?