UNIDAD II
Métodos de Ordenación Externa

            En la ordenación interna los registros están en todo momento en memoria principal, salvo cuando termina el proceso, que se vuelven a almacenar en el dispositivo externo. La memoria principal es limitada y por el contrario el número de registros de los que puede constar un archivo es elevado, tanto de no caber en memoria.
La ordenación de los registros de un archivo mediante archivos auxiliares se denomina ordenación externa. Los distintos algoritmos de ordenación externa utilizan el esquema general de separación y fusión o mezcla. Por separación se entiende la distribución de secuencias de registros ordenados en una única secuencia ordenada. Variaciones de este esquema general dan lugar a diferentes algoritmos de ordenación externa.

Por intercalación se entiende la unión o fusión de dos o más archivos, ordenados de acuerdo con un determinado campo clave, en un solo archivo.

Ejemplo: Suponga que se tienen dos archivos, F1 y F2, ordenados de acuerdo a un campo clave:

F1:  06   09   18    20    35
F2:  10   16   25    28    66    82    87

Debe producirse entonces en un archivo F3 ordenado, como resultado de la mezcla de F1 y F2. Sólo pueden ser accedidas directamente dos claves, la primera del archivo F1 y la segunda del archivo F2. Las comparaciones que se realizan para producir el archivo F3 son las siguientes:

(06 < 10)   sí se cumple la condición
Se escribe 06 en el archivo de salida F3 y se vuelve a leer otra clave de F1(09).

(09 < 10)   sí se cumple la condición
Se escribe 09 en el archivo de salida F3 y se vuelve a leer otra clave de F1(18).

(18 < 10)   no se cumple la condición
Se escribe 10 en el archivo de salida F3 y se vuelve a leer otra clave de F2(16).

El estado de los archivos F1, F2 y F3 es hasta el momento el siguiente:

El proceso continúa hasta que en uno u otro archivo se detecte el fin de archivo, en tal caso sólo tendrán que transcribir las claves del archivo no vacío al archivo de salida F3. Éste es el resultado final de la intercalación entre archivos F1 y F2:

F3:      06        09        10        16        18        20        25        28        35        66        82        87

2.2 Método de Ordenamiento por mezcla (Mergesort)

            Este es el método más simple que utiliza el esquema iterativo de separar secuencias y mezclarlas. Se trabaja con el archivo original y dos archivos auxiliares. El proceso consiste:

1. Separar los registros del archivo original F en dos mitades F1, F2.
2. Mezclar F1 y F2 combinando registros aislados (según sus claves) y formando pares ordenados que son escritos en el archivo F.
3. Separar pares de registros del archivo original F en dos mitades F1, F2.
4. Mezclar F1 y F2 combinando pares de registros y formando cuádruplos ordenados que son escritos en el archivo F.
5. Se repiten los pasos de separación y mezcla, combinando cuádruplos para formar óctuplos ordenados. En cada paso de separación y mezcla se duplica el tamaño de las subsecuencias mezcladas, así hasta que la longitud de la subsecuencia sea la que tiene el archivo y en ese momento el archivo F está ordenado.

Ejemplo:

Considérese un archivo que está formado por los registros de las claves enteras siguientes:

Pasada 1
            Separación:
                F1: 34   12   73   8   28
                F2: 23   59   44   19   51
            Mezcla formando duplos ordenados:
                F:  23   34   12   59   44   73   8   19   28   51
Pasada 2
            Separación:
                F1: 23   34    44    73    28    51
                F2: 12   59     8    19
            Mezcla formando cuádruplos ordenados:
                F:  12   23   34   59   8   19   44   73   28   51
Pasada 3
            Separación:
                F1: 12   23   34   59   28   51
                F2: 8   19   44   73
            Mezcla formando óctuplos ordenados:
                F:  8   12   19   23   34   44   59   73   28   51
Pasada 4
            Separación:
                F1: 8   12   19   23   34   44   59   73
                F2: 28   51
            Mezcla con la que ya se obtiene el archivo ordenado:
                F:  8   12   19   23   28   34   44    51   59   73

El tiempo de las comparaciones realizadas en la fase de fusión es insignificante respecto a las operaciones de movimiento de registros en los archivos externos. Por lo que no resulta interesante analizar el número de comparaciones.

HERRAMIENTAS, MATERIALES Y EQUIPOS:

• Hojas blancas, lápiz
• Lenguaje C#
• Pc

PROCEDIMIENTO:

• Resuelva cada uno de los ejercicios de acuerdo al procedimiento que se indica.
• Elabore el algoritmo de cada uno de los problemas planteados.
• Codifique los algoritmos en Lenguaje C#.
• Compruebe que la ejecución y sus resultados  sean correctos.

EVIDENCIAS:
            Documentos:

• Hoja de presentación
• Algoritmos de cada uno de los ejercicios.
• Diagramas de Flujo de cada método.
• Impresión del Código en el lenguaje C#.
• Impresión de la ejecución. (Pantalla con resultados)
• Conclusión.

           Programas:

• Toda la carpeta
• Todos los ejercicios serán entregados en un solo disco. (El disco debe traer su etiqueta correspondiente).

PLANTEAMIENTO DE PROBLEMAS

3.1.  Se leen dos listas de números enteros, A y B, de 20 y 15 elementos, respectivamente. Se desea resolver mediante métodos las siguientes tareas:

1. Ordenar cada una de las listas A y B.
2. Crear una lista C por intercalación de las listas A y B.
3. Visualizar la lista C ordenada.

3.2.   Leer una lista de números enteros, aplique el método de ordenamiento por mezcla y visualice el vector con la lista ya ordenada.

Conclusión

La ordenación de archivos se denomina, en general, ordenación externa y requiere algoritmos apropiados. Una manera trivial de realizar la ordenación de un archivo secuencial consiste en copiar los registros a otro archivo de acceso directo, bien relativo o secuencial indexado, usando como clave el campo por el que se desea ordenar.

Si se desea realizar la ordenación de archivos usando solamente como estructuras de almacenamiento de archivos secuenciales con un formato similar al que se desea ordenar, hay que trabajar usando el esquema de separación y mezcla.
En el caso de mezcla simple se opera con tres archivos análogos: el original y dos archivos auxiliares. El proceso consiste en  recorrer el archivo original y copiar los sucesivos registros en uno de los archivos auxiliares, mientras que dichos registros formen una secuencia ordenada.

Existen diferentes métodos avanzados de ordenación de archivos: mezcla equilibrada, mezcla múltiple, mezcla equilibrada múltiple y mezcla polifásica.

Cuando se tienen dos vectores ordenados y se necesita obtener otro también ordenado, el de intercalación proceso debe producirnos el resultado deseado, sin que sea necesario aplicar a continuación ningún método de ordenación.