Presentación algoritmos ordenación externa

Algoritmos de Ordenamiento Externos

INGENIERÍA EN SISTEMAS – 4TO CICLOMateo QuizhpiTania LandivarChristian Salinas

20/12/2016

UNIVERSIDAD DE CUENCAdesde 1867

Contenido

• Algoritmos de Ordenación Externa

• Intercalación Directa

• Intercalación Natural

• Intercalación Balanceada

• Intercalación Polifase

Algoritmos de Ordenación Externa

• La ordenación externa está ligada con los archivos y los dispositivos en que seencuentra, al leer el archivo para realizar la ordenación.• El tiempo de lectura de los registros es notablemente mayor.• Un archivo está creado por una secuencia de elementos, cada elemento es un

objeto(registro)• La ordenación externa de archivos se realiza con la ayuda de archivos auxiliares• Separación y mezcla

Intercalación Directa

• Algoritmo de ordenación externa más utilizado, probablemente por su fácil comprensión

• La idea central de este algoritmo radica en la realización sucesivade una partición y una fusión que produce secuencias ordenadas delongitud cada vez mayor

• Es importante señalar que la partición se inicializa de longitud 1mientras que la fusión produce secuencias ordenadas de longitud 2.En la siguiente pasada se duplicará dichas longitudes.

• El número de pasadas esta dado hasta que la longitud de lasecuencia para la partición sea Parte Entera ((n+1)/2), donde n es elnúmero de elementos a ordenar.

MetodologíaAl iniciar se cuenta con un archivo F (donde se encontralos elementos a ordenar), y también dos archivos Aux1 y Aux2 (que ayudarán en la partición).

Partición

Fusión

Partición

Fusión

Partición

Fusión

Partición

Fusión

Intercalación Natural

• Este método mejora el tiempo de ejecución de la mezcla directa alintroducir una pequeña variación respecto a la longitud de lassecuencias de los registros

• Pueden existir, de manera natural, secuencias de registros yaordenadas que también pueden mezclarse y dar lugar a otrasecuencia ordenada

• Este método, distribuye en todo momento secuencias ordenadas lomas largas posibles y mezcla secuencias ordenadas lo más largasposibles

• Utiliza de la misma manera que la mezcla directa, dos Archivos Auxiliares

• El método termina cuando uno de los archivo auxiliares está vacío.

Intercalación Natural

Intercalación Natural

Se tiene inicialmente el Archivo Original con todos los registros y dos archivos

Auxiliares vacíos.

Intercalación Natural

Se recorre el archivo Original y se separa las secuencias ordenadas más largas

en cada caso

Cada vez que encuentre una secuencia ordenada lo más larga posible, cambia

de archivo auxiliar para escribir el registro.

Separación

Intercalación Natural

Compara cada uno de los registros ordenados de cada Auxiliar, siempre que esten

ordenados, en el primer paso se comparo los registros que estaban en los bloques

plomos y los escribe en el archivo original.

Intercalación NaturalMezcla

Intercalación NaturalMezcla

Sigue comparando los registros que cada Auxiliar siempre que sea en secuencias

ordenadas, ahora se ordenaron las secuencias que estaban en amarillo.

Al ser la secuencias de registros en los bloques cafés, los ultimos ordenados, se agregan

al archivo Original

Intercalación NaturalMezcla

Finaliza el primer proceso de mezcla, con los archivo Auxiliares vacíos.

Intercalación NaturalSeparación

Nuevamente se recorre el archivo Original y se separa las secuencias

ordenadas más largas en cada caso

De la misma forma para cada secuencia ordenada se cambiar de archivo para

la separacion.

Intercalación NaturalMezcla

Se repite el proceso de mezcla para cada secuencia ordenada como en el primer

proceso de mezcla, siempre toma secuencias ordenadas de cada archivo Auxiliar.

Ordenados registros de bloques plomos.

Los registros amarillos, al ser los ultimos se agregan al archivo Original.

Intercalación NaturalMezcla

Finaliza el proceso de mezcla, con los archivo Auxiliares vacíos.

Intercalación NaturalSeparación

Nuevamente se realiza el proceso de separación, en este caso se tiene solo dos

secuencias ordenadas, cada una en un archivo Auxiliar.

Se ordena las últimas dos secuencias, en el archivo Original.

Intercalación NaturalMezcla

Archivo Original Ordenado.

Intercalación Balanceada

• La eficiencia de los metodos de ordenacion externa sondirectamente proporcional al número de pasadas.

• Una forma de reducir el número de pasadas es incrementando elnúmero de archivos auxiliares.

• Se utiliza x archivo Auxiliares, x/2 son de entrada y x/2 son de salida

Intercalación Balanceada (Pasos)

1. Distribuir registros del archivo original por tramos en los x/2 primeroarchivos auxiliares, estos serán los archivos de entrada.

2. Mezclar tramos de los x/2 archivos de entrada y escribirlosconsecutivamente en los x/2 archivos de salida.

3. Cambiar la finalidad de los archivos,los de entrada pasan a ser desalida y viceversa.

4. Se repite a partir del segundo paso hasta que quede un único tramo,entonces la secuencia está ordenada.

Ejemplo:

• Anteriormente el método de Intercalación balanceada utilizaba números iguales de archivos auxiliares de entrada y salida.

• El método de mezcla Polifase es una intercalación desbalanceada.

• Utiliza un número constante de archivo de entrada, pero no igual al número de archivos de salida.

Intercalación Polifase

Intercalación Polifase

• El método polifásico utiliza m archivos auxiliares para ordenar nregistros de un archivo.

• Considera m-1 archivos de entrada, en los cuales se mezclanregistros y un archivo de salida.

• Cuando uno de los archivos de entrada alcanza su final hay uncambio, este pasa a ser considerado como archivo de salida y elarchivo que en ese momento era de salida, pasa a ser de entrada yla mezcla de tramos continua.

Intercalación Polifase(pasos)

• Se tiene inicialmente los archivo de entrada que van a ser m-1 y uno solo de salida

• Se intercalan los registros de mayor tamaño en el archivo de salida.

• El archivo de entrada que primero queda vacio pasa a ser el archivo de salida.

• Se repiten los dos ultimos pasos, hasta que un archivo de salida contenga los registros ordenados.

En la primera distribucion los registros se reparten en dos archivos auxiliares de

entrada (F1 y F2) para ser escritos en el archivo de salida (F3).

Intercalación PolifaseIntercalación Polifase

Intercalación PolifaseIntercalación Polifase

Nuevos archivo de entrada F1 y F3

Archivo único de Salida F2

El Archivo de entrada, que primero queda vacio, pasa

a ser el archivo de salida.

Intercalación PolifaseIntercalación Polifase

Nuevos archivo de entrada F2 y F3

Archivo único de Salida F1

Intercalación PolifaseIntercalación Polifase

Nuevos archivo de entrada F1 y F2

Archivo único de Salida F3

BIBLIOGRAFÍA

Aguilar, L. J., & Martínez, I. Z. (s.f.). Estructura de datos en Java. España.