7.1.1 Intercalacion Directa

Ordenación por mezcla directa

El metodo de ordenacion por mezcla directa es probablemente el más utilizado por su facil comprension. La idea central de este algoritmo consiste en la realization sucesiva de una particion y una fusion que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada, la particion es de longitud 1 y la fusion o mezcla produce secuencias ordenadas de longitud 2. En la segunda pasada, la particion es de longitud 2 y la fusion o mezcla produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la secuencia para la particion sea:
Parte entera ((n +l)/2).

Donde n representa el número de elementos del archivo original.

Ejemplo. Supongamos que se desea ordenar las claves del archivo F. Para realizar tal actividad se utilizan los archivos auxiliares a los que se les denominara F1 y F2.

F:    09    75    14    68    29    17    31    25    04    05    13    18    72   46    61

PRIMERA PASADA

Particion en secuencias de longitud 1.

F1:  09'    14'    29'    31'    04'    13'    72'    61'
F2:  75'    68'    17'    25'    05'    18'    46'

Fusión en secuencias de longitud 2.

F:    09    75'    14    68'    17    29'    25    31'    04    05'    13    18'    46    72'    61'

SEGUNDA PASADA

Partición en secuencias de longitud 2.

F1:    09    75'    17    29'    04   05'    46    72'
F2:    14    68'    25    31'    13   18'    61'

Fusión en secuencias de longitud 4.

F:    09    14    68    75'    17    25    29    31'    04    05    13    18'    46    61    72'

TERCERA PASADA

Particion en secuencias de longitud 4.

F1:    09    14    68    75'    04    05    13    18'
F2:    17    25    29    31'    46    61    72'

Fusión en secuencias de longitud 8.

F:    09    14    17    25    29    31    68    75'    04    05    13    18    46    61    72'

CUARTA PASADA

Particion en secuencias de longitud 8.

Fl:    09    14    17    25    29    31    68    75'
F2:    04    05    13    18    46    61    72'

Fusión en secuencias de longitud 16.

F:    04   05    09    13    14    17    18    25    29    31    46    61    68    72   75

A continuacion se presenta el algoritmo de ordenacion de archivos por el metodo de mezcla directa.

Mezcla_directa (F, Fl, F2, N)
El algoritmo ordena los elementos del archivo F por el metodo de mezcla directa. Utiliza archivos auxiliares F1 y F2. N es el número de elementos del archivo F PART es una variable de tipo entero.

1. Hacer PART <- 1
2. Mientras (PART < parte entera ((N + 1) / 2)) Repetir
           Llamar al algoritmo Particiona con F, F1, F2 y PART
           Llamar al algoritmo Fusiona con F, F1, F2 y PART
           Hacer PART <- PART * 2
3. Fin del ciclo del paso 2

Observe que el algoritmo requiere para su funcionamiento de dos algoritmos liares, los cuales se presentan a continuacion.

Particiona (F, Fl, F2, PART)
El algoritmo genera dos archivos auxiliares, Fl y F2, a partir del archivo F. PART es longitud de la partition que se va a realizar K, L y R son variables de tipo entero

1. Abrir el archivo F para lectura.
2. Abrir los archivos F1 y F2 para escritura.
3. Mientras (no sea el fin de archivo de F) Repetir
          Hacer K <- 0
3.1. Mientras ((K < PART) y (no sea el fin de archivo de F)) Repetir 
           Leer R de F 
           Escribir R en Fl
           Hacer K <- K + 1
3.2. {Fin del ciclo del paso 3.1}
Hacer L <- 0
3.3. Mientras ((L < PART) y (no sea el fin de archivo de F)) Repetir 
           Leer R de F
           Escribir R en F2
           Hacer L <- L + 1
3.4 Fin del ciclo del paso 3.3
4. Fin del ciclo del paso 3

Fusiona (F, Fl, F2, PART)
El algoritmo fusiona los archivos F1 y F2 en el archivo F. PART es la longitud de la partición que se realizo previamente R1, R2, K y L son variables de tipo entero. Bl y B2 son variables de tipo booleano

1. Abrir el archivo F para escritura.
2. Abrir los archivos F1 y F2 para lectura.
3. Hacer B1 <- VERDADERO y B2 <- VERDADERO
4. Si (no es el fin de archivo de Fl) entonces 
       Leer B1 de F1
       Hacer B1 <- FALSO
5. {Fin del condicional del paso 4}
6. Si (no es el fin de archivo de F2) entonces 
       Leer R1 de F2 Hacer B2 <- FALSO
7. Fin del condicional del paso 6
8. Mientras ((no sea el fin de archivo de Fl) o (Bl = FALSO)) y ((no sea el fin de archivo de F2) o (B2 = FALSO)) Repetir
        Hacer K <- 0 y L <- 0
        8.1. Mientras ((K < PART) y (Bl = FALSO)) y ((L < PART) y ((B2 = FALSO)) Repetir
                     8.1.1. Si (R1 ≤ R2)
                             entonces
                                      Escribir B1 en F
                                      Hacer B1 <- VERDADERO y K <- K +1
                                      8.1.1.1 Si (no es el fin de archivo de F1) entonces
                                                         Leer R1 de F1
                                                         Hacer B1 <- FALSO
                                      8.1.1.2. Fin del condicional del paso 8.1.1.1
                             si no
                                         Escribir R1 en F
                                         Hacer B2 <- VERDADERO  y L <-L+1
                                          8.1.1.3 Si (no es el fin de archivo de F2) entonces
                                                      Leer R2 de F2
                                                      Hacer B2 <- FALSO
                                          8.1.1.4. Fin del condicional del paso 8.1.1.3
                     8.1.2 Fin del condicional del paso 8.1.1
        8.2 {Fin del ciclo del paso 8.1}
        8.3. Mientras ((K < PART) y (Bl = FALSO)) Repetir
                        Escribir R1 en F
                        Hacer B1 <- VERDADERO y K  <- K +1
                        8.3.1. Si (no es el fin de archivo de F1) entonces
                                    Leer R1 de F1
                                    Hacer B1 <- FALSO
                       8.3.2 Fin del condicional del paso 8.3.1
        8.4. Fin del condicional del paso 8.3
        8.5. Mientras ((L < PART)  y  (B2 = FALSO)) Repetir 
                        Escribir R2 en F
                        Hacer B2 <- VERDADERO y L <- L + 1
                        8.5.1. Si (no es el fin de archivo de F2) entonces 
                                Leer R2 de F2
                                Hacer B2 <- FALSO
                       8.5.2 Fin del condicional del paso 8.5.1
       8.6. Fin del ciclo del paso 8.5
9. Fin del ciclo del paso 8
10. Si (B1 = FALSO) entonces
        Escribir R1 en F 
11. Fin del condicional del paso 10
12.  Si (B2 = FALSO) entonces
             Escribir R2 en F
13. Fin del condicional del paso 12
14. Mientras (no sea el fin de archivo de F1) Repetir
        Leer R1 de F1
        Escribir R1 en F
15. Fin del condicional del paso 14
16. Mientras (no sea el fin de archivo de F2) Repetir
        Leer R2 de F2
        Escribir R2 en F
17. Fin del ciclo del paso 16
18. Cerrar los archivos F, Fl y F2