ordenamiento externo

Algoritmo de ordenamiento externo intercalación

Intercalación
En este método de ordenamiento existen dos archivos con llaves ordenadas, los cuales se mezclan para formar un solo archivo la longitud de los archivos puede ser diferente. El proceso consiste en leer un registro de cada archivo y compararlos, el menor es almacenando en el archivo de resultado y el otro se compara con elsiguiente elemento del archivo si existe. El proceso se repite hasta que alguno de los archivos quede vacío y los elementos del otro archivo se almacenan directamente en el archivo resultado.
EJEMPLO:
Inicio {
abrir archivo A
abrir archivo B
abrir archivo X
a = leer archivo A
b = leer archivo B
procesa los dos archivos
mientras (!eof(A) && !eof(B)){
si (a < b) { almacena en X a
a = leer archivoA }
sino { almacena en X b
b = leer archivo B }
}
procesa archivo A
mientras (!eof(A)){
almacena en X a
a = leer archivo A }
procesa archivo B
mientras (!eof(B)){
almacena en X b
b = leer archivo B }
cerrar archivos A,B,X
} Este código está en pseudocodigo

EL SIGUIENTE ES EL EJEMPLO :





5.2.3. ALGORITMO DE ORDENAMIENTO EXTERNO MEZCLA NATURAL





Ordenamientoexterno: Mezcla Natural (Natural Merge Sort) 
El método de Mezcla Natural consiste en aprovechar la existencia de secuencias ya ordenadas dentro de los datos de los archivos. A partir de las secuencias ordenadas existentes en el archivo, se obtienen particiones que se almacenan en dos archivos o ficheros auxiliares. Las particiones almacenadas en estos archivos auxiliares se fusionan posteriormentepara crear secuencias ordenadas cuya longitud se incrementa arbitrariamente hasta conseguir la total ordenación de los datos contenidos en el archivo original.

Para ilustrar la Mezcla Natural es muy conveniente utilizar números enteros como los datos almacenados en un archivo, de tal manera que este método funciona como se ilustra en el siguiente ejemplo (se utilizan corchetes o paréntesiscuadrados para separar las secuencias en las particiones):

Nombre del archivo original: Origen
Archivos auxiliares: Auxiliar1 y Auxiliar2
Origen: [10,17],[5,8,9],[3,22,50],[4],[2,20,30],[11,16,19],[6,21,23]


Primera Iteración:

Las secuencias que se encuentren dentro del archivo origen se almacenan de forma alternada en los archivos auxiliares:

ParticiónAuxiliar1: [10,17],[3,22,50],[2,20,30],[6,21,23]

Auxiliar2: [5,8,9],[4,11,16,19]
La fusión se realiza por pares de secuencias de manera ordenada, así, la primer nueva secuencia está formada por los elementos de la primera secuencia en el archivo Auxiliar 1 y los elementos de la primera secuencia en el archivo Auxiliar2. Si uno de los archivos auxiliares llega a su fin, las secuencias que se encuentren en el otro archivo sinterminar se vacían directamente después de las nuevas secuencias:

Fusión en el archivo original

Origen: [5,8,9,10,17],[3,4,11,16,19,22,50],[2,20,30],[6,21,23]


Segunda Iteración:

Se repite el proceso de partición con las nuevas secuencias:

Partición

Auxiliar1: [5,8,9,10,17],[2,20,30]

Auxiliar2: [3,4,11,16,19,22,50],[6,21,23]
Cuando al comparar un par de secuencias en losarchivos auxiliares una de ellas llega a su fin, entonces simplemente se vacía el resto de la secuencia que aún contiene elementos en la nueva secuencia. Este caso se observa claramente en el par de secuencias azules: cuando se llega al elemento 17 del archivo Auxiliar1, la nueva secuencia en la fusión simplemente incluye los elementos 19, 22 y 50 del archivo Auxiliar2 al final.

Fusión en elarchivo original

Origen: [3,4,5,8,9,10,11,16,17,19,22,50],[2,6,20,21,23,30]


Tercera Iteración:

En este punto se cuenta ya con sólo un par de secuencias. La fusión de éstas da como resultado una secuencia que contiene todos los elementos del archivo Origen en orden ascendente.

Partición

Auxiliar 1: [3,4,5,8,9,10,11,16,17,19,22,50]

Auxiliar 2: [2,6,20,21,23,30]


Fusión...