Explicación sencilla de OSort.
El algoritmo es básicamente un QuickSort, al revés y usando busqueda binaria.
Proviene de la idea (fundamental) de que ordenar n elementos de un vector, es equivalente a hacer un “merge” de n vectores ordenados de un elemento (un vector ordenado de un elemento, es un elemento desordenado, lógico).
Por lo tanto lo que hallé es la forma de mezclar n vectores ordenados de forma óptima.
Como estaba convencido de que era una generalización de la búsqueda binaria (ya que es ordenación por comparación), no fué “tan” dificil:
Si quieres mezclar n vectores ordenados en un sólo vector ordenado, tan sólo has de coger el vector central, elegir su elemento central como pivote y situarlo dentro de los vectores que se encuentren en el centro de cada mitad. Pero para eso los elementos de los otros vectores tienen que estar ya situados respecto al resto, es recursivo.
Simplificando, cada elemento ha de buscarse únicamente en dos vectores, uno anterior y uno posterior, de forma recursiva y mediante búsqueda binaria y ¡voilá!
January 30th, 2008 at 01:38
Esto es mejor que Programación Dinámica para un problema de unión de eslabones con coste (peso)?
January 31st, 2008 at 13:04
Sinceramente, no entiendo que quieres decir.
Esto es sólo la solución a un problema muy concreto, el numero minimo de comparaciones para ordenar elementos de un vector. Y de paso el numero minimo de comparaciones para fusionar n vectores.
No es la forma más rápida, sólo la que hace menos comparaciones (se puede hacer lo mismo sin comparaciones, mediante interpolación…). Sólo hace falta ver que una tabla hash es más rápida que una búsqueda binaria.
Por otro lado yo sólo veo una implementación estática de este algoritmo.
Puede que una implementación dinámica sea más rápida, por minimizar el movimiento de datos.
Vale, creo que ya he entendido xD.
A ver, ¿hablas de fusionar vectores mediante programación dinámica, no?
Si son vectores de datos ordenados y no consecutivos, y los quieres fusionar mediante comparaciones, esto te dará la forma de minimizar el numero de comparaciones. Si lo puedes/sabes hacer mediante otro método que no use comparaciones, probablemente sea más rápido.
(Perdona el tocho).
P.D.: Me ha encantado el video en tu blog de “Programar Dibujando”.