METODO POR INTERCALACION

Thursday, May 04, 2006

MÉTODO DE INTERCALACIÓN

ALGORITMO ORDENACIÓN POR INTERCALACIÓN

OBJETIVOS

Conocer los pasos y procedimientos que lleva a cabo el algoritmo de ordenación por intercalación.

Identificar las ventajas y desventajas que este algoritmo tiene contra los otros ya vistos en el curso de la materia.

Enunciar las características del algoritmo de ordenación por intercalación y demostrar mediante un código dicho algoritmo.

Analizar en donde, cuando y por qué podemos utilizar el mencionado algoritmo.

DESARROLLO

El resultado al aplicar la operación de ordenamiento es encontrar una permutación de un conjunto de elementos tal que exista una relación de orden entre los N elementos tomados en secuencia, ya sea en orden ascendente o descendente.

PARÁMETRO DE EVALUACIÓN PARA ORDENAMIENTOS

Los principales parámetros que se tienen en cuenta para un ordenamiento son los siguientes:

La rapidez para ejecutar.

La cantidad de memoria utilizada (su importancia ha disminuido).

Respecto a la rapidez para ordenar, normalmente se trata de medir la calidad del algoritmo con base en el número de comparaciones que se deben efectuar. Se encuentra que los ordenamientos lineales (basados en listas) son en general más lentos que los ordenamientos no lineales (basados en estructuras de árbol).

La diferencia del número de comparaciones se debe a la estructura que utilizan.

En cuanto a la memoria a utilizar (a pesar de su incremento en los computadores en los últimos años), en muchos casos no es suficiente debido a que la cantidad de datos por ordenar normalmente es grande, lo que hace que no toda la información se pueda almacenar en memoria principal.

ORDENACIÓN POR INTERCALACIÓN (MERGESORT)

El proceso de intercalar consiste en unir N listas ordenadas para conformar una lista ordenada única. Las listas que se van a intercalar se ordenan por un campo y la resultante después de la operación de intercalamiento es una lista ordenada de acuerdo con dicho campo.

El tiempo de ejecución es de O(n log n), y el número de comparaciones es casi óptimo. Se trata de un buen ejemplo fino de un algoritmo recursivo.

Debido a que las listas están ordenadas, esto se puede hacer en una pasada sobre la entrada, si la salida se pone en una tercera lista. El algoritmo de intercalación básico toma dos arreglos de entrada a y b, un arreglo de salida c, y tres contadores, apa, apb, apc, los cuales primero se ponen al inicio de sus arreglos respectivos. El menor de a[apa] y b[apb] se copia en la siguiente entrada de c, y se avanzan los contadores apropiados. Cuando se agota cualquier lista de entrada, los datos que queden en la otra lista se copian en c. Un ejemplo de cómo funciona la rutina se da para la siguiente entrada.

1 13 24 26 2 15 27 38
i j k

Si el arreglo a contiene 1, 13, 24, 26 y b 2, 15, 27, 38, el algoritmo procede como sigue: primero, se hace una comparación entre 1 y 2. El elemento 1 se agrega a c, y después se comparan 13 y 2.

El 2 se agrega a c, y luego se comparan 13 y 15.

1 13 24 26 2 15 27 38 1 2
i j k
El 13 se agrega a c, y después se comparan 24 y 15. Esto continua hasta comparar 26 y 27.


1 13 24 26 2 15 27 38 1 2 13
i j k


1 13 24 26 2 15 27 38 1 2 13 15
i j k

1 13 24 26 2 15 27 38 1 2 13 15 24
i j k

26 se agrega a c, y se agota el arreglo a.


1 13 24 26 2 15 27 38 1 2 13 15 24 26
i j k


El resto del arreglo b se copia en c.


1 13 24 26 2 15 27 38 1 2 13 15 24 26 27 38
i j k


Desde luego, el tiempo para combinar dos arreglos ordenados es lineal porque a lo más se hacen n-1 comparaciones, donde n es el número total de elementos. Para ver esto, observe que todas las comparaciones agregan un elemento al arreglo c, excepto la última, que agrega dos.

Por lo tanto es fácil describir el algoritmo mergesort. Si n = 1, solo hay un elemento por ordenar, y la respuesta está a la mano. Este algoritmo es una estrategia clásica de “divide y vencerás”. El problema se divide en dos problemas menores y se resuelve recursivamente. La fase de vencer consiste en pegar las dos respuestas. “Divide y vencerás” es un uso muy potente de la recursión que veremos muchas veces.

El algoritmo mergesort utiliza como auxiliar al metodo de intercalación. El metodo de fusión empieza de datos desordenados, divede en dos el número de elementos del vector, reconoce una parte izquierda y una parte derecha. De la parte izquierda divide en dos nuevamente para reducir el número de elementos en diferentes vectores y así sucesivamente hasta que los vectores quedan con un solo elemento para después comparar de dos en dos y ordenarlos aplicando el método de intercalación hasta llegar a ordenar la parte izquierda del vector original. Se aplica el mismo procedimiento para ordenar el vector de la parte derecha.