Hoy os voy a descubrir una pequeña maravilla del arte independiente.
Una serie cojonuda (y no es porque en ella participen mi padre y sobre todo, mi primo Jorge).
Como la vida misma, http://www.averlasvenir.es/
32 minutos de metraje, que me han pasado realitavamente cómo 5.
Un ejemplo de cómo con pocos medios y menos actores, puede hacerse una serie mucho mejor que las “profesionales”.
P.D.: ¡QUIERO UN PAPEL! xD Yo tambien tengo mi historia…
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 ;).
He modificado la imagen que en wikipedia ilustra Mergesort (de dominio público) para mostrar como funciona mi Optimal Comparison Sort.Recuerdo que para mezclar tres vectores, se usa el Merge3.
Aprovecho para comentar que es el equivalente a un árbol balanceado.Las comparaciones en este caso son 10 para mi Optimal Comparison Sort , 14 para Mergesort y 15 para Quicksort eligiendo como pivote el elemento central. Espero un comportamiento proporcional para vectores aleatorios más grandes. Read the rest of this entry »
Sabemos la forma óptima de mezclar tres vectores ordenados, la de mezclar cuatro no será tan sencilla. Read the rest of this entry »
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. Read the rest of this entry »
De momento (creo que) tenemos el algoritmo de merge óptimo para dos vectores… pero nuestro objetivo va más allá.La idea es hallar un merge para N vectores, pero como no parece fácil, vayamos pasito a pasito.Lo hemos hecho para dos, intentémoslo para tres vectores. Sean tres vectores, v1, v2 y v3, parece que una generalización del algoritmo anterior debería de empezar por comparar los centros, al menos uno de ellos.Como queremos que el merge sea estable, las posiciones de los vectores si que importan, por lo tanto empezaremos por el vector central.
v1: |1|2|3|4|5|6|7|8|9|v2: |1|2|3|4|5|6|7|8|9|
v3: |1|2|3|4|5|6|7|8|9|
Seguimos comparando centros de vectores, por lo tanto elegiremos el central de los centros como pivote, y empezaremos por comapararlo con los otros dos centros.
Tenemos 5<=5<=5.
Por lo tanto:
v1: |6|7|8|9|v2: |1|2|3|4|5|6|7|8|9|
v3: |1|2|3|4|
Ahora tenemos 7>5>2, por tanto:
v1: |6|v2: |1|2|3|4|5|6|7|8|9|v3: |3|4|
6>5>3
v1: v2: |1|2|3|4|5|6|7|8|9|v3: |4|
5>4
En resumen, hemos separado los tres vectores en relación a nuestro pivote que era el elemento más central, por ser del que más información se obtiene al compararlo.
Tenemos
|1|2|3|4|5| |6|7|8|9|
|1|2|3|4| 5 |6|7|8|9|
|1|2|3|4| |5|6|7|8|9|
Tán sólo nos queda repetir la operación de forma recursiva, y tenemos el mejor merge que haya visto un mergesort, usandolo en lugar del merge tradicional, se reduciría el número de comparaciones y sobre todo el movimiento de datos, al mezclar los vectores de forma óptima de tres en tres.
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 |
A parte de su interés practico evidente (ordenar datos rápido), un algoritmo “óptimo” supone un gran reto.