Metodo De Intercalacion
Páginas: 3 (624 palabras)
Publicado: 14 de noviembre de 2012
MÉTODO DE INTERCALACIÓN
ALGORITMO ORDENACIÓN POR INTERCALACIÓN
ORDENACIÓN POR INTERCALACIÓN (MERGESORT)
El proceso de intercalar consiste en unir N listas ordenadas para conformar una listaordenada ú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 deejecució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 enuna 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 cualquierlista 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 acontiene 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, yluego 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 1324 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 bse 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...
ALGORITMO ORDENACIÓN POR INTERCALACIÓN
ORDENACIÓN POR INTERCALACIÓN (MERGESORT)
El proceso de intercalar consiste en unir N listas ordenadas para conformar una listaordenada ú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 deejecució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 enuna 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 cualquierlista 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 acontiene 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, yluego 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 1324 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 bse 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...
Leer documento completo
Regístrate para leer el documento completo.