No se puede hacer un algoritmo óptimo en el número de comparaciones para todos los casos.
Me temo, que hoy, sin querer, he demostrado que el mejor algoritmo de ordenación no puede tener n-1 comparaciones para datos ordenados. La mala noticia es que las comparaciones para un algoritmo “óptimo” serán siempre superiores a n-1. La buena es que demostrando esto he encontrado un algoritmo de ordenación óptimo, tan óptimo como es posible.Todo empieza con mi merge de 3 vectores. Es óptimo en el número de comparaciones para tres vectores cualquiera, esto incluye ordenar 3 elementos de forma óptima. El problema empieza al generalizarlo. No encontraba ningún algoritmo que lo generalice, siendo óptimo para un vector de N elementos ordenados. ¿Porque? Porque es imposible que sea óptimo para el caso mejor con n-1 comparaciones y el caso peor.
Demostración a continuación:
Queremos ordenar con el mínimo de comparaciones posibles N datos, por lo tanto necesitaremos crear un árbol binario de N nodos. Para facilitar la tarea usaremos 7 datos (por forma un árbol binario lleno y perfecto -o árbol completo).
Supongamos el vector: |1|2|3|4|5|6|7|, vamos a ordenarlo ;).
Sabemos la forma óptima de ordenar tres elementos, de modo que, ordenemos de forma óptima los tres primeros y los tres últimos, para depues ordenar todos juntos.
Tenemos |1|2|3| con dos comparaciones y |5|6|7| con otras dos. Ahora falta ordenar el |4|, si queremos tener el minimo de comparaciones (n-1), por lo tanto, necesitamos comparar el 4 con el 3 y con el 5. PERO, si comparamos primero con el 3 y con el 5, hacemos que el caso peor, necesite , al menos una comparación extra.Esto es así porque no hacemos el equivalente a lo que sería una búsqueda binaria para localizar la posición del elemento central en los dos vectores ordenados. Como sabemos que la búsqueda binaria es la forma más rápida de media de buscar un elemento en un vector ordenado, el algoritmo óptimo no podrá ser así.
Por lo tanto el algoritmo óptimo de ordenación por comparación SIEMPRE, hará más de n-1 comparaciones.
Después de esto es fácil deducir el algoritmo óptimo, que presentaré en el siguiente post.
Ya sé que como demostración no es muy rigurosa, ni sigue un modelo formal, pero a partir del ejemplo no debería de ser difícil generalizarla, y no quiero perder el tiempo con algo que ahora veo trivial.