Vectores cruzados (o la solución conceptual al problema de la optimización de la ordenación por comparación).
La idea básica la tuve este verano, pensando en dimensiones, vectores y dimensiones; ¿Si tomamos un vector como una dimensión, habría media dimensión si por ejemplo sólo coges terminos positivos? Y chorradas así.
Pero lo que de verdad importa es la siguiente idea, para ordenar N vectores ordenados, los podemos ver como N dimensiones. Por lo tanto si juntamos esos vectores en un plano N-dimensional, pudiera ser que fuera muy fácil hacer la fusión (merge) -Violeta, si algún momento lees esto, en eso es en lo que estaba pensando este verano :P-.
Para muestra un botón (uso 3 vectores, por no saber representar más de 3 dimensiones en el plano, vectores de 3 elementos para facilitar la búsqueda binaria, y son sin repetición para evitarme más problemas de momento) :
Así un algoritmo casi óptimo, adaptativo, de ordenación por comparación sería así:
Para que fuera óptimo de verdad la única variación sería comparar siempre los elementos centrales de los vectores (busqueda binaría). Siempre hacia el vector central. Sería equivalente a mi idea de un algoritmo óptimo recursivamente adaptativo.
Como se puede ver es una forma mucho más sencilla de representar y trabajar con la ordenación de vectores.
Creo que aplicando esta estructura como TAD (tipo abstracto de datos) adecuado, se pueden conseguir el numero mínimo de comparaciones para la ordenación. El TAD creo que sería un gráfo dirigido con algún añadido para localizar los centros de los vectores (también puede que sea más fácil de dibujar que n dimensiones).
Es increíble lo importante que es la busqueda binaria para desarrollar estas ideas. al fin y al cabo está en todos lados… y sino…¿Tú como cortaría el queso si quieres hacer dados con el mínimo de cortes? Por la mitad y otra vez por la mitad, hasta que los pedazos sean suficientemente pequeños.
P.D.: Le estoy dando vueltas a que puede que sea imposible hacer un algoritmo superadaptativo (recursivamente adaptativo) que a la vez sea óptimo, me da la impresión de que si comparas primero todos los centros de todos los vectores estás haciendo comparaciones que no son imprescindibles.
El algoritmo óptimo por lo tanto sería: inserción binaria del elemento central de los vectores colindantes, en el vector central, e inserción binaria recursiva de los elementos centrales de sus dos mitades, luego repetimos la operación para el resto de los vectores. Tal vez si primero ordenamos los centros de todos los vectores, nos ahorremos comparaciones, o tal vez no, y sólo fueran operaciones prescindibles, si lo implemento después de examenes, probaré las dos posibilidades.