Presentacion algoritmos ordenacion externa

  • View
    102

  • Download
    4

Embed Size (px)

Text of Presentacion algoritmos ordenacion externa

Algoritmos de Ordenamiento Externos

Algoritmos de Ordenamiento ExternosINGENIERA EN SISTEMAS 4TO CICLOMateo QuizhpiTania LandivarChristian Salinas

20/12/2016

UNIVERSIDAD DE CUENCAdesde 1867

1

Contenido

Algoritmos de Ordenacin ExternaIntercalacin DirectaIntercalacin NaturalIntercalacin BalanceadaIntercalacin Polifase

2

Algoritmos de Ordenacin ExternaLa ordenacin externa est ligada con los archivos y los dispositivos en que se encuentra, al leer el archivo para realizar la ordenacin.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 ordenacin externa de archivos se realiza con la ayuda de archivos auxiliaresSeparacin y mezcla

3

Intercalacin DirectaAlgoritmo de ordenacin externa ms utilizado, probablemente por su fcil comprensinLa idea central de este algoritmo radica en la realizacin sucesiva de una particin y una fusin que produce secuencias ordenadas de longitud cada vez mayorEs importante sealar que la particin se inicializa de longitud 1 mientras que la fusin produce secuencias ordenadas de longitud 2. En la siguiente pasada se duplicar dichas longitudes.El nmero de pasadas esta dado hasta que la longitud de la secuencia para la particin sea Parte Entera ((n+1)/2), donde n es el nmero de elementos a ordenar.

4

MetodologaAl iniciar se cuenta con un archivo F (donde se encontralos elementos a ordenar), y tambin dos archivos Aux1 y Aux2 (que ayudarn en la particin).

5

ParticinFusin

ParticinFusin

6

Particin

Fusin

ParticinFusin

7

Intercalacin NaturalEste mtodo mejora el tiempo de ejecucin de la mezcla directa al introducir una pequea variacin respecto a la longitud de las secuencias de los registros

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

Este mtodo, distribuye en todo momento secuencias ordenadas lo mas largas posibles y mezcla secuencias ordenadas lo ms largas posibles

8

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

El mtodo termina cuando uno de los archivo auxiliares est vaco.Intercalacin Natural

9

Intercalacin NaturalSe tiene inicialmente el Archivo Original con todos los registros y dos archivos Auxiliares vacos.

10

Intercalacin NaturalSe recorre el archivo Original y se separa las secuencias ordenadas ms largas en cada casoCada vez que encuentre una secuencia ordenada lo ms larga posible, cambia de archivo auxiliar para escribir el registro.Separacin

11

Intercalacin 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.Intercalacin NaturalMezcla

12

Intercalacin NaturalMezclaSigue 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 cafs, los ultimos ordenados, se agregan al archivo Original

13

Intercalacin NaturalMezclaFinaliza el primer proceso de mezcla, con los archivo Auxiliares vacos.

14

Intercalacin NaturalSeparacinNuevamente se recorre el archivo Original y se separa las secuencias ordenadas ms largas en cada casoDe la misma forma para cada secuencia ordenada se cambiar de archivo para la separacion.

15

Intercalacin NaturalMezclaSe 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.

16

Intercalacin NaturalMezclaFinaliza el proceso de mezcla, con los archivo Auxiliares vacos.

17

Intercalacin NaturalSeparacinNuevamente se realiza el proceso de separacin, 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.

18

Intercalacin NaturalMezclaArchivo Original Ordenado.

19

Intercalacin BalanceadaLa eficiencia de los metodos de ordenacion externa son directamente proporcional al nmero de pasadas.

Una forma de reducir el nmero de pasadas es incrementando el nmero de archivos auxiliares.

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

20

Intercalacin Balanceada (Pasos)Distribuir registros del archivo original por tramos en los x/2 primero archivos auxiliares, estos sern los archivos de entrada.

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

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

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

21

Ejemplo:

22

Anteriormente el mtodo de Intercalacin balanceada utilizaba nmeros iguales de archivos auxiliares de entrada y salida.

El mtodo de mezcla Polifase es una intercalacin desbalanceada.

Utiliza un nmero constante de archivo de entrada, pero no igual al nmero de archivos de salida.

Intercalacin Polifase

23

Intercalacin PolifaseEl mtodo polifsico 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.

24

Intercalacin 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 tamao 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.

25

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).

Intercalacin PolifaseIntercalacin Polifase

26

Intercalacin PolifaseIntercalacin Polifase

Nuevos archivo de entrada F1 y F3Archivo nico de Salida F2El Archivo de entrada, que primero queda vacio, pasa a ser el archivo de salida.

27

Intercalacin PolifaseIntercalacin Polifase

Nuevos archivo de entrada F2 y F3Archivo nico de Salida F1

28

Intercalacin PolifaseIntercalacin Polifase

Nuevos archivo de entrada F1 y F2Archivo nico de Salida F3

29

BIBLIOGRAFAAguilar, L. J., & Martnez, I. Z. (s.f.). Estructura de datos en Java. Espaa.