Ordenamiento y Mezcla de
Archivos
Presentado por:
Ing. Claudio Gutiérrez, MBA.
Objetivos
• Al finalizar la clase el alumno será
capaz de:
1. Definir la lógica de intercalación
2. Conocer las fase de ordenamiento de
archivos
3. Comprender los métodos de
intercalación a través de ejemplos
gráficos.
Lógica de Intercalación
• Tiene las sublistas de entrada ordenadas
por la llave que dirige la intercalación.
• Las listas de entrada no necesariamente
deben ser la misma longitud; cuando una
lista se termina el resto de la otra lista es
copiado en el archivo intercalado
resultante.
Ejemplo: Lógica de Intercalación
dos lista ordenadas
Fases de un ordenamiento de
Archivos
1. Fase de ordenamiento interno, en el cual
se ordenan los registros mediante varias
ejecuciones distribuidas en dos o mas
dispositivos de almacenamiento.
2. Fase de intercalación, en el cual se
combinan los subarchivos ordenados en
una sola ejecución.
3. Fase de salida, en la cual se copia el archivo
en su medio de almacenamiento final.
Aspectos que difieren en las técnicas de
ordenamiento/intercalación de archivos
1. El método de ordenamiento interno
aplicado
2. La cantidad de memoria principal asignada
al ordenamiento interno.
3. La distribución de las sublistas ordenadas
en memoria secundaria
4. El numero de sublistas ordenadas que han
de ser intercaladas en un paso de
intercalación.
Factores que afectan el desempeño, medidos de acuerdo
con el numero de veces que los registros son
leídos/escritos
1. Iniciar la fase de ordenamiento con subarchivos ordenados
tan grandes como sea posible, minimiza el numero de
sublistas que se deben intercalar.
2. A mayor numero de sublistas que son intercaladas a la vez,
menores serán, los pases necesarios para intercalar el
conjunto de sublistas.
3. La distribución de las sublistas en memoria secundaria para
entrar a un paso de la intercalación puede requerir procesos
de E/S adicionales al requerido para realizar la intercalación.
Métodos de Intercalación
• Intercalación natural
• Intercalación balanceada
• Intercalación polifase
• Intercalación de cascada
Intercalaciones Naturales
• Una intercalación de M vías
se define como una
intercalación con M archivos
de entrada y solo uno de
salida.
Ejemplo de una intercalación
natural de 2 vías
Ejemplo de una intercalación
natural de 3 vías
Intercalaciones balanceadas
• Una intercalación balanceada evita
mucho del copiado de registros, una y
otra vez, distribuyendo los resultados del
paso de intercalación directamente en el
numero apropiado de archivos para la
entrada al siguiente paso de intercalación.
Ejemplo de una intercalación
balanceada de 2 vías
Intercalaciones de Polifase
• Utiliza un numero constante de
archivos de entrada. Una
intercalación de polifase de M
vías usa 2M – 1 archivos de
entrada.
Ejemplo de Intercalación polifase
Determinación de la distribución de las
sublistas para una intercalación de polifase
Distribución de sublistas para una
intercalación de polifase
Intercalación de Cascada
• Una intercalación de cascada
descansa sobre una buena
distribución inicial de las
sublistas por la fase de
ordenamiento interno.
Ejemplo de intercalación de
cascada
Capacidades de ordenamiento/intercalación con
utilerías
Especificación del proceso de
ordenamiento/intercalación
Conclusiones
• Al finalizar la clase el alumno será
capaz de:
1. Define la lógica de intercalación
2. Conoce las fase de ordenamiento de
archivos
3. Comprende los métodos de
intercalación a través de ejemplos
gráficos.
