Metodos De Ordenamiento

INTEGRANTES:
1.-Cordova Medina Juan Pablo
2.-Guerrero Castillo Roberto
3.- Alanís López Oscar Daniel
4.- Zapote Baltazar José Juan

Unidad: IV

Grupo: 6B

Fecha: 02 de noviembre de 2012.

Contenido:
Métodos de Ordenamiento Externos

CONTENIDO

Ordenamiento Externos 
1. Intercalación
2. Mezcla Directa
3. Mezcla Natural

Objetivos
Durante este trabajo semostraran los métodos de ordenamiento externos, mostrando de forma más clara que son y cómo actúan estos temas dentro de la materia en cuestión.

1. Intercalación Balanceada: Una intercalación balanceada de m vías utiliza m archivos de entrada y m archivos de salida.
Las k listas ordenadas se distribuyen en forma uniforme en los m archivos de entrada. Se intercalan las listas de cada uno delos archivos, distribuyendo en forma uniforme las listas resultantes en los archivos de salida (de mayor tamaño que las iniciales). Se repite el último paso hasta que un archivo de salida contiene una lista ordenada. Las m vías a las que se hace mención, son las que limitarán el número de archivos que podremos utilizar para nuestro proceso de ordenamiento. El tamaño de las listas estará dado por lacapacidad del Buffer, con ello obtendremos el número de listas que tendremos que distribuir entre los m archivos de entrada.
Por ejemplo: Se desea ordenar un archivo con 6000 registros. Se cuenta con 2 vías para lograrlo y se sabe que el Buffer soporta un tamaño de listas de 1000 registros. Con todo, sabemos que tenemos que distribuir 6 listas (6000/1000) entre los 2 archivos de entrada (2 vías).Luego, dividiendo 6 por 2 no da 3 listas para cada archivo, las cuales tendrán un tamaño de 1000 registros (los que soporta el Buffer).

Como podemos apreciar, con cada intercalación el número de listas va disminuyendo, pero su tamaño en registro va aumentando, esto debido a que en cada intercalación se agregan registros a las listas y estos quedan en forma ordenada. Finalmente se llega a unasola lista que contiene todos los registros intercalado (ordenados).

 
2. Intercalación Natural: Una intercalación Natural de m vías utiliza m archivos de entrada y 1 archivo de salida.
Las k listas ordenadas se distribuyen en forma uniforme en los m archivos de entrada. Se intercalan las listas de cada uno de los archivos en el archivo de salida. Se distribuyen las listas que están en laarchivo de salida (de mayor tamaño que las iniciales) en forma uniforme (nuevamente) en los archivos de en los archivos de entrada que en este momento están vacíos. Se repiten los 2 últimos pasos hasta que el archivo de salida contiene una lista ordenada con todos los registros.
Ejemplo: Se desea ordenar un archivo con 3.000 registros. Se cuenta con 2 vías para lograrlo y se sabe que el Buffersoporta un tamaño de listas de 10 registros. Con todo, sabemos que tenemos que distribuir 300 listas (3000/10) entre los 2 archivos de entrada (2 vías). Luego, dividiendo 300 por 2 no da 150 listas para cada archivo, las cuales tendrán un tamaño de 10 registros (los que soporta el Buffer).

3. Intercalación Polifásica: Una intercalación polifásica de m vías utiliza 2*m-1 archivos de entrada y 1archivo de salida.
Las k listas se distribuyen en forma no uniforme en los 2*m-1 archivos de entrada. Se intercalan las listas (de mayor tamaño posible) en el archivo de salida. El archivo de entrada que primero queda vacío pasa a ser archivo de salida y el archivo de salida pasa a ser de entrada. Se repiten los 2 últimos pasos hasta que un archivo de salida contenga las lista ordenada.
Porejemplo: Se tiene un archivo de datos que contiene 129.000 registros. Las listas son de tamaño 1000 registros (los que soporta el Buffer) y el grado de la intercalación es 3 (m=3 vías). Nº Reg.= 129.000 m=3 Archivos de entrada = 2*m-1= 2*3-1=5 T/L = 1.000 reg. Nº Listas = 129 Archivos de Salida = 1 Ahora debemos distribuir las 129 listas en los 5 archivos de entrada, pero en forma no uniforma, lo...