Ordenación externa

Informática. Intercalación múltiple. Mezcla: directa e indirecta

  • Enviado por: Jesús Alonso
  • Idioma: castellano
  • País: España España
  • 7 páginas
publicidad

TEMA 4

ORDENACIÓN EXTERNA

…o como perder menos tiempo, y hacer menor número de accesos a la memoria.

INDICE TEMA 4.

4.1 Justificación

4.2 Ordenación por mezcla

  • Ordenación externa

  • 4.3.1. Mezcla directa

    4.3.2. Mezcla natural

    4.4. Intercalación múltiple

    1. JUSTIFICACIÓN

    Volumen de datos amplio

    Tamaño de memoria limitado

    Objetivo: minimizar el número de accesos a los ficheros

    2. ORDENACIÓN POR MEZCLA.

    • N ficheros `ordenados' de unen para formar un único archivo ordenado:

    A

    B

    Operación C

    Vacio

    Vacio

    nada

    Vacio

    No vacio

    copiar todos los registros de B en C

    No vacio

    Vacio

    copiar todos los registros de A en C

    No vacio

    No vacio

    bucle a repetir hasta que A o B estén vacios (*)

    (*) Operaciones a realizar en este caso:

    Leer ( A, ElemA )

    Leer ( B, ElemB )

    Bucle hasta llegar al final de A o B

    Comparar ( ElemA, ElemB )

    if ElemA > ElemB

    then Escribir ElemB en C

    Leer B

    else Escribir ElemA en C

    Leer A

    Introducir el resto de A o B en C

    3. ORDENACIÓN EXTERNA.

    • MEZCLA DIRECTA

    Se ordenan las secuencias de un archivo en grupos de tamaño creciente = 2n (1, 2, 4, 8, …):

    Sea la secuencia:

    22 6 25 48 32 5 12 20 31 35

    Para grupos de tamaño = 1, tenemos:

    22 25 32 12 31

    6 48 5 20 35

    Ordenando estas secuencias:

    6 , 22 25 , 48 5 , 32 12 , 20 31 , 35

    Agrupando en grupos de tamaño = 2:

    6 , 22 5 , 32 31 , 35

    25 , 48 12 , 20

    Ordenando estos grupos:

    6 , 22 , 25 , 48 5 , 12 , 30 , 32 , 31 , 35

    Agrupando en grupos de tamaño = 4:

    6 , 22 , 25 , 48 31 , 35

    5 , 12 , 20 , 32

    Ordenando:

    5 , 6 , 12 , 20 , 22 , 25 , 32 , 48 31, 35

    La ultima agrupación ( tamaño = 8 ):

    5 , 6 , 12 , 20 , 22 , 25 , 32 , 48

    31 , 35

    Ordenando:

    5 , 6 , 12 , 20 , 22 , 25 , 31 , 32 , 35 , 48

    El procedimiento a seguir es el siguiente:

  • Dividir la secuencia a ordenar en 2 subsecuencias de menor tamaño, cada una la mitad de la secuencia original.

  • Mezclar las dos secuencias de forma ordenada, para generar otra mayor, formada por cinjuntos ordenados de valores con 20, 21, 22, … elementos.

  • Iterar los pasos 1 y 2 hasta que el tamaño del conjunto ordenado (2n) sea mayor que el número de elemtentos a ordenar.

    • MEZCLA NATURAL

    Las secuencias intermedias no tienen tamaño prefijado ni longitud constante. Estas se generan con sus elementos ordenados, separando un elemento nuevo a otra secuencia si no se respeta esta condición.

    Se incluyen separadores de secuencia.

    Sea la cadena de numeros:

    F1:

    3 15 7 17 9 8 14 2 41 24 36 1 13 42 26 35 5 33

    Aplicando el método de mezcla natural con tres ficheros, uno original y dos auxiliares (frecuententemente llamados `cintas'), el resultado es:

    F2:

    3 15 9 2 41 1 13 42 5 33

    7 17 8 14 24 36 36 35

    Cap. 4 ORDENACIÓN EXTERNA

    p-5-