7.1.2 Mezcla Natural

Ordenación por el método de mezcla equilibrada

El método de ordenación por mezcla equilibrada, conocido tambien como natural, es una optimization del metodo de mezcla directa.

La idea central de este algoritmo consiste en realizar las particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias de tamaño fijo previamente determinadas. Luego se realiza la fusion de las secuencias ordenadas, en alternada, sobre dos archivos. Aplicando estas acciones en forma repetida se logrará el archivo original quede ordenado. Para la realization de este proceso de ordenación se necesitaran cuatro archivos. El archivo original F y tres archivos auxiliares a los que se denominara F1, F2 y F3. De estos archivos, dos serán considerados de entrada y dos de salida; esto, de manera alternada, con el objeto de realizar la fusion-partición. El proceso termina cuando en la realización de una fusion-partición el segundo archivo quede vacío.

Supongamos que se desea ordenar las claves del archivo F utilizando el método mezcla equilibrada.

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

Los pasos que se realizan son:

PARTICIÓN  INICIAL

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

PRIMERA FUSION-PARTICION

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

SEGUNDA FUSION-PARTICION

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

TERCERA FUSION-PARTICION

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

Observe que al realizar la tercera fusion-partición el segundo archivo queda vacío; por lo tanto, se puede afirmar que el archivo ya se encuentra ordenado. A continuación se presenta la description formal del algoritmo de mezcla equilibrada.

Mezcla_equilibrada (F, F1, F2, F3)
El algoritmo ordena los elementos del archivo F por el metodo de mezcla equilibrada. Utiliza tres archivos auxiliares F1, F2 y F3 BAND es una variable de tipo booleano

1. Llamar al algoritmo Particion inicial con F, F2 y F3
2. Llamar al algoritmo Particion fusion con F1, F3, F y F1 
3. Hacer BAND <- FALSO
4. Mientras ((F1 ≠ VACIO) o (F3 ≠VACIO)) Repetir
         4.1. Si (BAND = VERDADERO)
                  entonces
                        Llamar al algoritmo Particion_fusion con F2, F3, F y F1
                        Hacer BAND <- FALSO
                  si no
                        Llamar al algoritmo Particion_fusion con F, F1,F2 y F3
                        Hacer BAND <- VERDADERO
         4.2. Fin del condicional del paso 4.1
5. Fin del ciclo del paso 4

El algoritmo requiere para su funcionamiento de dos algoritmos auxiliares, Particion_inicial yParticion_fusion, los cuales se presentan a continuation.

Particion_inicial (F, F2, F3)El algoritmo produce la particion inicial del archivo F en dos archivos auxiliares, F2 y F3 AUX y R son variables de tipo entero. BAND es una variable de tipo booleano

1. Abrir el archivo F para lectura.
2. Abrir los archivos F2 y F3 para escritura.
3. Leer R de F.
4. Escribir R en F2.
5. Hacer BAND <- VERDADERO y AUX <- R 
6. Mientras (no sea el fin de archivo de F) Repetir
          Leer R de F
           6.1 Si (R a AUX)
                   entonces
                           Hacer AUX <-R
                           6.1.1 Si (BAND = VERDADERO)
                                           entonces
                                                  Escribir R en F2
                                           si no
                                                  Escribir R en F3
                           6.1.2. Fin del condicional del paso 6.1.1 
                   si no
                           Hacer AUX <- R
                           6.1.3. Si (BAND = VERDADERO) entonces
                                             Escribir R en F3
                                             Hacer BAND <- FALSO
                                      si no
                                             Escribir R en F2 
                                             Hacer BAND <- VERDADERO
                           6.1.4. Fin del condicional del paso 6.1.3
                      6.2. Fin del condicional del paso 6.1
7. Fin del ciclo del paso 6
8. Cerrar los archivos F, F2 y F3

Particion_fusion (FA, FB, FC, FD)

El algoritmo produce la particion y la fusion de los archivos FA y FB, en los archivos FC y FD R1, R2 y AUX son variables de tipo entero. BANl, BAN2 y BAN3 son variables de tipo booleano

1. Abrir los archivos FA y FBpara lectura.
2. Abrir los archivos FC y FD para escritura.
3. Hacer BAN1 <- VERDADERO, BAN2 <- VERDADERO,
                BAN3 <- VERDADERO y AUX <- -32 768  {AUX se inicializa con un valor negativo alto} 
4. Mientras ((no sea el fin de archivo de FA) o (BANl = FALSO)) y ((no sea el fin de archivo de FB) o ((BAN2 = FALSO)) Repetir
                4.1. Si (BAN1 = VERDADERO) entonces 
                                Leer R1 de FA
                                Hacer BAN1 <- FALSO
                4.2. Fin del condicional del paso 4.1
                4.3  Si (BAN2 = VERDADERO) entonces 
                                Leer R2 de FB 
                                Hacer BAN2 <- FALSO
                4.4. Fin del condicional del paso 4.3
                4.5. Si (R1 < R2) entonces 
                                4.5.1. Si (R1 ≥ AUX) entonces
                                                4.5.1.1.  Sí(BAN3 = VERDADERO)
                                                                entonces
                                                                                Escribir R1 en FC
                                                                si no
                                                                                Escribir R1 en FD
                                                4.5.1.2. Fin del condicional del paso 4.5.1.1
                                                Hacer BAN1 <- VERDADERO y AUX <-  R1 
                                           si no
                                                4.5.1.3.Si (BAN3 = VERDADERO)
                                                                entonces
                                                                                Escribir R2 en FC 
                                                                                Hacer BAN3 <- FALSO
                                                                si no
                                                                                Escribir R2 en FD
                                                                                Hacer BAN3 <- VERDADERO
                                                  4.5.1.4 Fin del condicional del paso 4.5.1.3
                                                   Hacer BAN2 <- VERDADERO y AUX <- -32 768
                                4.5.2. Fin del condicional del paso 4.5.1
                           si no 
                                4.5.3 Si (R2 ≥ AUX)
                                                entonces 
                                                                4.5.3.1. Si (BAN3 = VERDADERO)
                                                                                entonces
                                                                                                Escribir R2 en FC
                                                                                si no 
                                                                                                Escribir R2 en FD 
                                                                4.5.3.2. Fin del condicional del paso 4.5.3.1
                                                                Hacer BAN2 <- VERDADERO y AUX <- R2
                                                Si no 
                                                                4.5.3.3. Si (BAN3 = VERDADERO)
                                                                                entonces
                                                                                                Escribir R1 en FC
                                                                                                Hacer BAN3 <- FALSO
                                                                                si no
                                                                                                Escribir  R1 en FD
                                                                               Hacer BAN3 <- VERDADERO
                                                                4.5.3.4. Fin del condicional del paso 4.5.3.3
                                                                Hacer BAN1 <- VERDADERO y AUX <- -32 768
                                4.5.4. Fin del condicional del paso 4.5.3
                4.6. Fin del condicional del paso 4.5
5. Fin del ciclo del paso 4
6. Si (BAN1 = FALSO) entonces 
                6.1. Si (BAN3 = VERDADERO)
                                entonces
                                                Escribir R1 en FC
                                                6.1.1. Mientras (no sea el fin de archivo de FA) Repetir 
                                                                Leer R1 de FA
                                                                Escribir R1 en FC
                                                6.1.2. Fin del ciclo del paso 6.1.1
                                si no
                                                Escribir R1 en FD
                                                6.1.3. Mientras (no sea el fin de archivo de FA) Repetir
                                                                Leer R1 de FA 
                                                                Escribir R1 en FD
                                                6.1.4.Fin del ciclo del paso 6.1.3 
                6.2. Fin del condicional del paso 6.1 
7. Fin del condicional del paso 6
8. Si (BAN2 = FALSO) entonces 
                8.1 Sí'(BAN3=VERDADERO)
                                entonces
                                Escribir R2 en FC 
                                8.1.1 Mientras (no sea el fin de archivo de FB) Repetir
                                                Leer R2 de FB
                                                Escribir R2 en FC 
                                8.1.2 Fin del ciclo del paso 8.1.1 
                        si no
                                Escribir R1 en FD
                                8.1.3. Mientras (no sea el fin de archivo de FB) Repetir
                                                Leer R2 de FB
                                                Escribir R2 en FD
                                8.1.4. Fin del ciclo del paso 8.1.3
                8.2. Fin del condicional del paso 8.1
9. Fin del condicional del paso 8
10.Cerrar los archivos FA, FB, FC y FD

Ejemplo en lenjuage C

void mezclaEquilibrada(int archf, int archf1, int archf2, int archf3){
    int archivo_vacio=ARCHIVO_NINGUNO;
    boolean band;
    particionInicial(archf, archf2, archf3);
    //imprimir("después de partición inicial");
    band = true;
    do{
        if(band){
            particionFusion(archf2, archf3, archf, archf1);
            //imprimir("después de partición fusión con band=true");
            band=false;
        }else{
            particionFusion(archf, archf1, archf2, archf3);
            //imprimir("después de partición fusión con band=false");
           band=true;
        }

        abrirL(archf1);
        if(fin(archf1)) archivo_vacio=ARCHIVO_F1;
        cerrar(archf1);

        if(archivo_vacio==ARCHIVO_NINGUNO){
           abrirL(archf3);
            if(fin(archf3)) archivo_vacio=ARCHIVO_F3;
            cerrar(archf3);
        }
    }while(archivo_vacio==ARCHIVO_NINGUNO);
    imprimir("al final");
    printf("el archivo que está vacío es: %d\nEl listado final está en el: %d\n",
    archivo_vacio, archivo_vacio-1);
}

void particionInicial(int archf, int archf2, int archf3){

    registro aux, r;
    /* Si band==true, el último registro se escribió en f2,
    * sino, fue en f3
    */
    boolean band;

    abrirL(archf);
    abrirE(archf2);
    abrirE(archf3);

    if(!leer(archf, &r)){
        printf("Archivo vacío\n");
        cerrar(archf);
        cerrar(archf2);
        cerrar(archf3);
        exit(0);
    }
    escribir(archf2,r);
    band=true;
    aux=r;
    while(!fin(archf)){
        leer(archf, &r);
        if(r>=aux){
            aux=r;
            if(band){
                escribir(archf2,r);
            }else{
            escribir(archf3,r);
        }
        }else{
            aux=r;
            if(band){
               escribir(archf3,r);
                band=false;
            }else{
              escribir(archf2,r);
              band=true;
          }
       }
    }

    cerrar(archf);
    cerrar(archf2);
    cerrar(archf3);
}

void particionFusion(int archfa, int archfb, int archfc, int archfd){
    registro aux, r1, r2;
   boolean band, dele1, dele2;

    abrirL(archfa);
    abrirL(archfb);
    abrirE(archfc);
    abrirE(archfd);

    band = true;
    leer(archfa, &r1);
    leer(archfb, &r2);
    if(r1<=r2)
        aux = r1;
    else
        aux = r2;
    dele1 = dele2 = false;
    while((!fin(archfa) || dele1!=true) && (!fin(archfb) || dele2!=true)){
        if(dele1){
           leer(archfa, &r1);
           dele1=false;
        }
        if(dele2){
            leer(archfb, &r2);
            dele2=false;
        }
        if(r1<r2){
           if(r1>=aux){
                //printf("probando... aux %d, r1 %d, r2 %d\n", aux, r1, r2);
                ayuda1(&aux, r1, archfc, archfd, band);
                dele1=true;
            }
            else if(r2>=aux){
            //printf("probando... r1 %d, aux %d, r2 %d\n", r1, aux, r2);
                ayuda1(&aux, r2, archfc, archfd, band);
                dele2=true;
            }
           else{
                //printf("probando... r1 %d, r2 %d, aux %d\n", r1, r2, aux);
                ayuda2(&aux, r1, archfc, archfd, &band);
                dele1 = true;
            }
        }
        else{
            if(r2>=aux){
            //printf("probando... aux %d, r2 %d, r1 %d\n", aux, r2, r1);
                ayuda1(&aux, r2, archfc, archfd, band);
                dele2=true;
            }
            else if(r1>=aux){
            //printf("probando... r2 %d, aux %d, r1 %d\n", r2, aux, r1);
                ayuda1(&aux, r1, archfc, archfd, band);
                dele1=true;
            }
            else{
            //printf("probando... r2 %d, r1 %d, aux %d\n", r2, r1, aux);
                ayuda2(&aux, r2, archfc, archfd, &band);
                dele2 = true;
            }
        }
    } //fin del while
    if(dele1 && fin(archfa))
    ayuda3(&aux, r2, archfb, archfc, archfd, &band);
    if(dele2 && fin(archfb))
    ayuda3(&aux, r1, archfa, archfc, archfd, &band);

    cerrar(archfa);
    cerrar(archfb);
    cerrar(archfc);
    cerrar(archfd);
}