170 Ordenamiento, Búsqueda e Intercalación 7.3 Método de intercalación El método de Intercalación, también conocido como Merge en inglés, consiste en intercalar los valores de dos arreglos ordenados de igual manera, tal que se forme un tercer arreglo igual- mente ordenado con los elementos de los dos arreglos originales.Considerando dos arreglos ordenados en forma ascendente: A = (1, 7, 18, 23) B = (2, 5, 6, 9, 12, 16, 17) se trata de componer un nuevo arreglo ordenado: C = (1, 2, 5, 6, 7, 9, 12, 16, 17, 18, 23) donde los elementos de C se han obtenido intercalando las de A y B. Un criterio muy poco eficiente para resolver el problema sería construir un arreglo D colo- cando los elementos de B a continuación de los de A y luego reordenarlo partiendo de D = (1, 7, 18, 23,2, 5, 6, 9, 12, 16, 17)En esta forma se pierde la ventaja de que A y B ya hayan sido ordenados, y aumenta el tiempo de ejecución. El método de Intercalación compara los primeros elementos de A y de B y coloca en C el menor de ellos (por estar ordenados en forma ascendente), descartando dicho elemento. Luego continúa con los restantes, hasta que alguno de los dos arreglos se haya traspasado completa- mente a C, quedando las últimas componentes del otro arreglo por pasar. En el caso del ejemplo, los valores del arreglo B serán pasados a C, quedando el 18 y el 23 del arreglo A por pasar. Algoritmo intercalar arreglo [1,10000] real: A, B arreglo [1,20000] real: C ! C debe contener las comp. de A y las de B entero: n, m, i, inda, indb inicio Leer (n) ! cantidad de componentes de A Repetir Para i 1, n Leer (A[i]) finpara Leer (m) ! cantidad de componentes de B Repetir Para i 1, m Leer (B[i]) finpara inda 1 indb 1 ! próxima componente en cada arreglo ! intercalación Repetir Para i 1, n+m ! llenar cada componente de C Si (inda <= n y indb <= m) entonces ! hay componentes disponibles Si (A[inda] < B[indb]) entonces C[i] A[inda]
Created with BuildVu