30
Algoritmos de Ordenamiento Externos INGENIERÍA EN SISTEMAS – 4TO CICLO Mateo Quizhpi Tania Landivar Christian Salinas 20/12/2016 UNIVERSIDAD DE CUENCA desde 1867

Presentacion algoritmos ordenacion externa

Embed Size (px)

Citation preview

Algoritmos de Ordenamiento ExternosINGENIERÍ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 se encuentra, 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 sucesiva de una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor

• Es importante señalar que la partición se inicializa de longitud 1 mientras 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 la secuencia para la partición sea Parte Entera ((n+1)/2), donde n es el nú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 al introducir una pequeña variación respecto a la longitud de las secuencias de los registros

• Pueden existir, de manera natural, secuencias de registros ya ordenadas que también pueden mezclarse y dar lugar a otra secuencia ordenada

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

• 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 NaturalSe tiene inicialmente el Archivo Original con todos los registros y dos archivos Auxiliares vacíos.

Intercalación NaturalSe 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 NaturalCompara 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 Natural Mezcla

Intercalación Natural Mezcla

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 Natural Mezcla

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 Natural Mezcla

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 Natural Mezcla

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 Natural Mezcla

Archivo Original Ordenado.

Intercalación Balanceada• La eficiencia de los metodos de ordenacion externa

son directamente proporcional al número de pasadas.

• Una forma de reducir el número de pasadas es incrementando el nú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 primero archivos auxiliares, estos serán los archivos de entrada.

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

3. Cambiar la finalidad de los archivos,los de entrada pasan a ser de salida 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 n registros de un archivo.

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

• Cuando uno de los archivos de entrada alcanza su final hay un cambio, este pasa a ser considerado como archivo de salida y el archivo que en ese momento era de salida, pasa a ser de entrada y la 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 F3Archivo ú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 F3Archivo único de Salida F1

Intercalación PolifaseIntercalación Polifase

Nuevos archivo de entrada F1 y F2Archivo único de Salida F3

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