Joel

INSTITUTO TECNOLOGICO DEL LLANO

Carrera: Lic. En informática

Alumno: Joel Vargas Díaz

Numero de control: 09900053

Grado y grupo: 4b

Materia: organización de datos

Docente: Francisco Valdez Silva

Unidad I

Tema: algoritmos de ordenamiento

Trabajo numero 5

13 de abril de 2011

ALGORITMOS DE ORDENAMIENTO EXTERNOS
Intercalación Balanceada: Unaintercalació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 de los 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 salidacontiene 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 la capacidad 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 6000registros. 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).
Intercalación Natural: Una intercalaciónNatural 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 la archivo de salida (de mayor tamaño que las iniciales) en forma uniforme (nuevamente) en los archivos de en los archivos deentrada 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 Buffer soporta un tamaño de listas de 10 registros. Con todo, sabemos que tenemos que distribuir 300 listas (3000/10) entre los 2archivos 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).

Intercalación Polifásica: Una intercalación polifásica de m vías utiliza 2*m-1 archivos de entrada y 1 archivo 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.
Por ejemplo: Se tiene un archivo de datos que contiene 129.000 registros. Las listas son de tamaño 1000 registros (los que soporta elBuffer) 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 que haremos como sigue:
Intercalación de Cascada: Una intercalación de cascada 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. Esta intercalación se realiza por medio de fases. Cada fase dura hasta que queda sólo un archivo con listas y luego se vuelve a comenzar con los archivos que fueron de salida en intercalaciones anteriores. Luego, el procedimiento a seguir es el siguiente: se intercalan las listas (de mayor tamaño...