azrael

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.

 Ahora cabe observar, que este merge, que es equivalente a ordenar tres elementos de un vector, sigue exactamente los mismos pasos que haría quicksort con tres elementos. Elige como pivote el elemento central, y lo compara con los otros dos, separando en un casó optimo, los tres elementos ordenados, o en el peor de los casos, separando uno de los datos como menor o mayor y ordenando recursivamente los otros dos datos.Es decir, Quicksort es óptimo para 3 elementos, exactamente lo que buscamos, hace un mínimo de dos comparaciones y un máximo de 3 para ordenarlos.Pero con más de 3 elementos eso ya no es cierto. Si continuamos usando el elemento central como pivote, independientemente de los resultados de la comparaciones, nos encontramos con que si el vector esta ordenado no iremos comparando los elementos contiguos. Esto lleva a quicksort a su peor caso. Si los elementos estan ordenados en orden creciente o decreciente, las comparaciones son O(n^2). Quicksort en un vector ordenado, eligiendo como pivote el elemento central es de O( n log n), pero sigue habiendo un caso de O(n^2), si cada pivote que eliges es máximo o minimo de los restantes elementos. Eso conlleva, que el merge óptimo de 4 vectores deja de ser sencillo.De hecho aún no tengo una idea muy clara de como debe hacerse, he hecho cientos de hipotesis pero en todas he acabado encontrando fallos (con los merges de 2 y 3 tambien me ha pasado, pero esos, creo que ya los tengo solucionados).Esta mañana se me ha ocurrido una idea increible, me ha recordado a Emmett Brown dándose un golpe en la cabeza y viendo de repente el condensador de fluzo. La idea no es tán buena, ya que sigue dejando casos de O(n^2).Puede que sea una chorrada, pero estoy convencido que todos los algoritmos de ordenación “buenos” son algoritmos incompletos, todos tienen partes de uno mejor. Lo que yo busco es que en el caso de que los datos estén ordenados, el algoritmo sólo haga n-1 comparaciones, y que el caso peor se resuelva de la mejor forma posible, así que ¿que tal una mezcla de Quicksort con Mergesort y puede que incluso con un poquito de Bubblesort?Me explico, la idea es elegir un primer pivote, que ha de ser el elemento central, despues se compara este con el siguiente y el anterior, igual que haría un quicksort en su primer paso, pero, la diferencia esta aquí, si esos tres elementos están ordenados (en orden creciente o decreciente), es decir, si ambas comparaciones son iguales, en lugar de seguir comparando, pasaría a haber dos pivotes, uno a cada lado del pivote anterior. Cada pivote iría comprobando que los siguientes elementos siguen el mismo orden, y en el momento que eso ya no sea así, el vector ordenado que hemos obtenido se guardará, para hacer un merge con los vectores ordenados que obtengamos en cada uno de los lados (llamadas recursivas).De momento he estado probando con cuatro elementos y parece óptimo, en el mejor caso son 3 comparaciones y en el peor 5.Esto no es así, porque sigue estando el caso de que el pivote sea máximo o minimo, es decir, el algoritmo sería O(n log n) de media, con O(n) para un vector ordenado, pero con casos “malos” de O(n^2).Recordemos esta lista que contiene los valores conocidos, de la serie del número mínimo de comparaciones para ordenar un vector en el peor caso.

Son: 

| 0 | 1 | 3 | 5 | 7 | 10 | 13 | 16 | 19 | 22 | 26 | 30 | 34 | 38 |

  

Para:

| 1 | 2 | 3 | 4 | 5 |  6 |  7 |  8 | 9  | 10 | 11 | 12 | 13 | 14 |

  

  

 

 

         

 

 

 

 

This entry was posted on Thursday, November 15th, 2007 at 20:43 and is filed under II CUSL, algoritmia. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.