11.5 Aplicación: análisis de la eficiencia de un algoritmo II 773 Una observación importante acerca del algoritmo por mezcla previamente descrito...

11.5 Aplicación: análisis de la eficiencia de un algoritmo II 773

Una observación importante acerca del algoritmo por mezcla previamente descrito: requiere memoria para mover los elementos del arreglo. Se necesita un segundo conjunto de posiciones del arreglo junto con el arreglo original, para así colocar en orden a los elementos de los dos subarreglos. En la figura 11.5.4 este segundo conjunto de posiciones se representa por las posiciones al fondo del tablero. De hecho, uno de los elementos del arreglo original se han colocado en este nuevo arreglo, se pueden mover de regreso, en orden, hacia las posiciones del arreglo original. Sin embargo, en términos de tiempo, la mezcla es eficiente porque el número total de comparaciones necesario para mezclar dos subarreglos en un arreglo de longitud k es exac- tamente k ฀ 1. Puede ver el porqué al analizar la figura 11.5.4. Observe que en cada etapa, la decisión sobre qué tarjeta mover se hace comparando los números sobre las tarjetas de los fondos de las dos columnas, excepto cuando una de las columnas está vacía, en cuyo caso no se realizan comparaciones. Así, en el peor caso habrá una comparación para cada una de las k posiciones en el arreglo final excepto el último (porque cuando se coloca la última tarjeta en posición, la otra columna seguramente estará vacía) o un total de k ฀ 1 comparaciones. El algoritmo de ordenamiento por mezcla es recursivo: sus enunciados de definición incluyen referencias a sí mismo. Sin embargo, el algoritmo está bien definido porque en cada etapa la longitud del arreglo que es introducida al algoritmo es más corta que en la etapa previa, así, finalmente, el algoritmo tiene que ocuparse sólo con arreglos de longitud 1, que ya están ordenados. Específicamente, el ordenamiento por mezcla funciona como sigue. Dado un arreglo de elementos susceptibles de poder ser ordenados, si el arreglo consiste de un solo elemento, déjelo como está. Ya está ordenado. En casos diferentes: 1. Divida el arreglo en dos subarreglos de aproximadamente la misma longitud. 2. Use el ordenamiento por mezcla para ordenar cada subarreglo. 3. Mezcle entre sí a los dos subarreglos. La figura 11.5.5 muestra un ordenamiento por mezcla en un caso particular.