azrael

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á!

He subido a la forja de rediris  los algoritmos que funcionan de lo que llevo escrito .

No es aún, el algoritmo de ordenación definitivo, pero se le acerca.

De momento, el algoritmo más rápido  es poco más o menos igual de rápido que Quicksort, pero se debe exclusivamente a la implementación, pues en ambas implementaciones uso o(n log n) memoria auxiliar (un autentico despilfarro).

Está en camino una implementación con un uso de memoría constante (es decir, un algoritmo in-place), pero requiere bastante trabajo. De momento tengo los algoritmo escritos de forma recursiva, pero “conociendo” a los compiladores, más vale que los escriba de forma iterativa a mano.

Creo que la mejor versión será usando el algoritmo de merge que he llamado (muy original) oMerge (de óptimo).

Una vez que tenga ese algoritmo en su versión iterativa, prescindiré de algoritmos auxiliares, y escribiré un algoritmo con una sola recursión, como el de Quicksort. Pero creo que se puede ir más allá y eliminar esa recursión tambien, ya que al contrario que en quicksort, las llamadas recursivas del algoritmo principal no dependen de las anteriores.

Bueno, el que quiera ya puede probar las diferentes velocidades de los diferentes merges. Trastenado un poquito con el código fuente, tambien los tipos de ordenación, pero ya digo que de momento, no he escrito AÚN nada mucho más rápido que mergesort.

Feliz navidad y feliz año ;).

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. (more…)

Ordenar N elementos será igual que ordenar N vectores ordenados de un elemento.Esta operación es la fusión de vectores (merge), y conseguir el merge óptimo de N vectores ordenados sería equivalente al algoritmo de ordenación óptimo.De momento sabemos la forma de buscar un elemento en un vector, pero lo que necesitamos es el merge de dos vectores.Por lo tanto intentemos generalizar el algoritmo de búsqueda binaria, para dos vectores. El mejor algoritmo de merge conocido hasta el momento es muy simple, y dados dos vectores de a y b elementos respectivamente, siempre hace a+b-1 comparaciones.Evidentemente ese algoritmo no es el que buscamos, pero nos dará una cota de lo que buscamos que sea el peor caso para el merge de dos vectores.

Empecemos. Tenemos dos vectores, v1 y v2 

v1: |1|2|3|4|5|6|7|8|9| 

v2:|1|2|3|4|5|6|7|8|9|

Como queremos generalizar la búsqueda binaria, lo que es evidente es que la primera comparación a realizar será comparar los dos centros. 5<=5Tras ello, querremos situar uno de los dos centros comparados dentro del otro vector. La elección igual que con el redondeo en búsqueda binaria, no parece tener mucha importancia. Por las mismas razones que antes, elegiremos el primer centro de los dos.  Este elemento será nuestro pivote, para esta iteración del algoritmo.Por lo tanto:  

v1: |1|2|3|4|5|6|7|8|9| 

v2:|1|2|3|4|

5>2 

v1: |1|2|3|4|5|6|7|8|9| 

v2:|3|4|

5>3

v1: |1|2|3|4|5|6|7|8|9| 

v2:|4|

5>4

Por lo tanto, tenemos la posición del elemento central del primer vector en el segundo. Es decir, hemos separado los datos de la forma siguiente.

|1|2|3|4|   |5|    |6|7|8|9|

|1|2|3|4|            |5|6|7|8|9|

Podemos repetir la operación recursivamente, para los vectores que nos quedan a la izquierda de nuestro pivote por un lado, y para los vectores que nos quedan a la derecha de nuestro pivote por el otro. 

Ya tenemos un algoritmo de merge de dos vectores, óptimo en el número de comparaciones.

Como prueba de que no me equivoco, el numero de comparaciones siempre es igual o inferior al del merge clásico (a+b-1 para dos vectores de tamaño a y b).

Intuitivamente, creo que un algoritmo óptimo de ordenación por comparación, será una generalización de la búsqueda binaría.¿Porqué?Porque la búsqueda binaría es el algoritmo óptimo de búsqueda la posición de un elemento entre otros elementos ordenados. Esto se debe a que si tenemos N elementos ordenados, y como única operación la comparación, la operación que más información nos dará será siempre comparar con el elemento central, de esta forma a cada paso descartamos la mitad de los elementos a comparar.

Por ejemplo, si buscamos la posición el dato D en el vector V: 

i)                          V= |1|2|3|4|5|6|7|8|9 |                                        D=6 

Nuestra primera comparación será preferentemente 5<=6, ya que  5 es el elemento central del vector.  Así, descartamos las comparaciones con los elementos anteriores al 5 (y con el 5).

ii)                     V1= |6|7|8|9|      D=6 

Al quedar un número par de elementos, podemos elegir entre el redondeo a la izquierda o a al derecha, en terminos de valor medio, ambas elecciones resultan en la misma cantidad de comparaciones, sin embargo, en los computadores, las cachés hacen que en general los accesos secuenciales, de izquierda a derecha sean más rápidos. Aunque puede que eso no suponga una diferencia significativa, lo que es evidente es que no va a resultar peor.Por lo tanto la comparación será 7>6, con lo que descartamos todos los elementos superiores al 7, y el 7.

iii)                    V2= |6|                            D=6 

Comparamos 6<=6, por lo tanto tenemos el vector |6|6| ordenado.Lo juntamos con los “trozos” de vectores que hemos ido descartando, y nos da el resultado  |1|2|3|4|5|6|6|7|8|9 | 

(more…)

A parte de su interés practico evidente (ordenar datos rápido), un algoritmo “óptimo” supone un gran reto.

(more…)