Algoritmo de Ordenamiento externo por Mezcla Equilibrada

De Wikilibros, la colección de libros de texto de contenido libre.

Algoritmo de Ordenamiento externo por Mezcla Equilibrada:

/*
    Este código es un simulador de ordenación externa con arreglos.
    El contenido inicial se toma de un archivo de tecto con el siguiente formato:

    {comienzo_de_archivo}{registro1}{retorno_de_carro}{registro2}{retorno_de_carro}
    {registro3}...{registroN}{fin_de_archivo}

    En realidad es muy sencillo, todos los registros están separados por un
    retorno de carro, pero después del último registro, no debe haber retorno de carro. ;-P

    He aquí un ejemplo:
        09
        29
        ...
        36
        11
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARCHIVO_ORIGEN  "prueba.txt"
#define NUM_ELEM 35

#define ARCHIVO_NINGUNO -1
#define ARCHIVO_F  0    //auxiliares
#define ARCHIVO_F1 1
#define ARCHIVO_F2 2
#define ARCHIVO_F3 3

#define FIN -1

typedef enum boolean{false, true} boolean;
typedef int registro;
typedef enum abertura{cerrado, lectura, escritura} abertura;


//archivos
int f[4][NUM_ELEM];
//posición del cursor para cada archivo
int ix[4];
//estado de cada archivo
abertura abierto[4];


void abrirL(int archivo);
void abrirE(int archivo);
void cerrar(int archivo);
void escribir(int archivo, int valor);
boolean leer(int archivo, registro *r);
boolean fin(int archivo);
void imprimir(const char *msg);

void mezclaEquilibrada(int archf, int archf1, int archf2, int archf3);
void particionInicial(int archf, int archf2, int archf3);
void particionFusion(int archfa, int archfb, int archfc, int archfd);
void ayuda1(registro *aux, registro r, int fc, int fd, boolean band);
void ayuda2(registro *aux, registro r, int fc, int fd, boolean *band);
void ayuda3(registro *aux, registro r, int f, int fc, int fd, boolean *band);



/*
    Ordenación externa por
    Mezcla Equilibrada
*/
int main(int argc, char *argv[]){

    FILE *fuente=NULL;
    int c;
    int i;

    fuente=fopen(ARCHIVO_ORIGEN, "r");
    if (fuente==NULL) {
        printf("\n--No se pudo habrir el archivo de entrada: %s--\n", ARCHIVO_ORIGEN);
        exit(1);
    }

    i=0;
    abrirE(ARCHIVO_F);
    while(fscanf(fuente, "%d", &c)>0 && i++<NUM_ELEM)
        escribir(ARCHIVO_F, c);
    fclose(fuente);
    cerrar(ARCHIVO_F);

    // para ponerle FIN a todas las posiciones
    abrirE(ARCHIVO_F1); cerrar(ARCHIVO_F1);
    abrirE(ARCHIVO_F2); cerrar(ARCHIVO_F2);
    abrirE(ARCHIVO_F3); cerrar(ARCHIVO_F3);


    //correr el algoritmo
    mezclaEquilibrada(ARCHIVO_F, ARCHIVO_F1, ARCHIVO_F2, ARCHIVO_F3);

    system("PAUSE");
    return 0;
}

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);
}

void ayuda1(registro *aux, registro r, int fc, int fd, boolean band){
    *aux = r;
    if(band){
        escribir(fc, r); //fputs("\n", fc);
    }else{
        escribir(fd, r); //fputs("\n", fd);
    }
    //imprimir("ayuda1");
}
void ayuda2(registro *aux, registro r, int fc, int fd, boolean *band){
    *aux = r;
    if(*band){
        escribir(fd, r); //fputs("\n", fd);
        *band=false;
    }
    else{
        escribir(fc, r); //fputs("\n", fc);
        *band=true;
    }
    //imprimir("ayuda2");
}
void ayuda3(registro *aux, registro r, int f, int fc, int fd, boolean *band){
    if(r>=*aux)
        ayuda1(aux, r, fc, fd, *band);
    else
        ayuda2(aux, r, fc, fd, band);
    while(leer(f, &r)){
        if(r>=*aux)
            ayuda1(aux, r, fc, fd, *band);
        else
            ayuda2(aux, r, fc, fd, band);
    }
    //imprimir("ayuda3");
}

//Abre el archivo para lectura
void abrirL(int archivo){
    ix[archivo]=0;
    abierto[archivo]=lectura;
}

//Abre el archivo para escritura
void abrirE(int archivo){
    int i;
    if(abierto[archivo]!=cerrado){
        printf("archivo %d, abierto, no se puede volver a abrir\n", archivo);
        //system("pause");
        exit(1);
    }
    ix[archivo]=0;
    abierto[archivo]=escritura;
    for(i=0; i<NUM_ELEM; i++)
        f[archivo][i]=FIN;
}

void cerrar(int archivo){
    ix[archivo]=0;
    abierto[archivo]=cerrado;
}

void escribir(int archivo, int valor){
    if(abierto[archivo]!=escritura){
        printf("archivo %d, cerrado, no se puede escribir\n", archivo);
        exit(1);
    }
    f[archivo][ix[archivo]++]=valor;
}

//retorna verdadero si hay un registro que leer,
//retorna falso, si se ha alcanzado el fin del archivo
boolean leer(int archivo, registro *r){
    if(abierto[archivo]!=lectura){
        printf("archivo %d, cerrado, no se puede leer", archivo);
        exit(1);
    }
    *r = f[archivo][ix[archivo]++];
    if (f[archivo][ix[archivo]-1]!=FIN)
        return true;
    else{
        ix[archivo]--;
        return false;
    }
}

//responde si se ha alcanzado el fin del archivo
boolean fin(int archivo){
    return f[archivo][ix[archivo]]==FIN;
}

void imprimir(const char *msg){
    int i, j;
    printf("\n%s:\n", msg);
    for(i=0; i<4; i++){
        printf("Archivo %d (estado: %d):\n", i, abierto[i]);
        for(j=0; j<NUM_ELEM; j++){
            printf("%02d ", f[i][j]);
        }
        printf("\n");
        for(j=0; j<ix[i]; j++)
            printf("   ");
        printf("|-> %d\n\n", ix[i]);
    }
    printf("---\n\n\n");
    system("PAUSE");
}

// fin del código