azrael

Sabemos la forma óptima de mezclar tres vectores ordenados, la de mezclar cuatro no será tan sencilla. Queremos ordenar n datos por comparación, por lo tanto sabemos que necesitamos localizarlos en un arból binario equilibrado. El problema de Quicksort es intentar crear ese árbol de arriba a abajo y no de abajo a arriba, y ahora veremos porqué.Sea un vector de 7 elementos.La mejor operación que sabemos realizar es ordenar 3 elementos, si la realizamos para los elementos a la izquierda y a la derecha del centro, hemos creado dos árboles binarios (vectores ordenados, de los que el elemento central será el padre). Ahora sólo falta situar el elemento central en esos dos árboles/vectores ordenados, la forma óptima es el merge 3 que ya hemos desarrollado.  Esto lo hemos hecho para un vector de 7 elementos para visualizarlo más fácilmente, pero podemos generalizarlo fácilmente. Crear un árbol binario con el elemento central del vector como raíz y recursivamente con sus lados, después vas ordenando desde la profundidad K hasta arriba. En pseudocódigo:  

 function Sort (v:vector) return v  

medio:=(v’primero+v’ultimo/2);  

return merge3(sort(v(v’primero..medio-1),v(medio),sort(v(v’medio+1..v’ultimo));

fin 

 Si no fuera por el merge3, sería más corto que Quicksort.En los próximos días lo implementaré, haré unas pruebas a ver si no sólo hace el numero mínimo de comparaciones, si no también es el más rápido (y sino porqué), y luego dejaré estar esto un tiempo, para estudiar (que ya me toca). Llevo dándole vueltas desde marzo del 2007. Si no me sobra tiempo antes, en febrero haré la implementación para el II CUSL.De momento hasta aquí he llegado con la ordenación ;). 

This entry was posted on Tuesday, November 20th, 2007 at 01:30 and is filed under Algoritmos ordenación., General, 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.