Ir al contenido

Simulación de algoritmos/Ordenamiento/Externo/Mezcla Equilibrada

Añadir enlaces
De Wikilibros, la colección de libros de texto de contenido libre.

Algoritmo de Ordenamiento externo por Mezcla Equilibrada escrito en lenguaje C estándar:


Descripción

[editar]

Este código es un simulador de ordenación externa con arreglos en lugar de archivos.

Se ha hecho un intento por mostrar gráficamente en la consola el proceso de actualización de los archivos de intercambio temporal. El autor espera que sea útil. :)

Ejecución

[editar]

Faltan algunos gráficos de su ejecución.

Compilación y ejecución de la versión actual

[editar]

El código está probado y funciona siendo compilado bajo linux con el gcc,tcc y no requiere ninguna biblioteca adicional.

Recibe como parámetro, en línea de comandos, un archivo preexistente con la estructura descrita en la sección de comentarios. Esto con el objetivo de proveer una simulación realista, gracias a que el archivo se puede modificar antes de cada ejecución para mostrar la efectividad del programa.

Ejemplo de ejecución: $: ./nombre_programa <archivo_con_los_números>

Mejoras deseables

[editar]
  1. Quizá una versión con fopen, fwrite y fread sea también útil.

Código del Simulador 1

[editar]
/*
    Este código es un simulador de ordenación externa con arreglos.
    El contenido inicial se toma de un archivo de texto 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" //Ahora toma el nombre de archivo desde el argumento del programa
#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(argv[1], "r"); 
    if (fuente==NULL) {
        printf("\n--No se pudo abrir el archivo de entrada: %s--\n", argv[1]);
        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);
    printf("\nPresione una tecla para continuar...\n"); //mensaje que reemplaza el usado por Windows en system("pause");
    getchar(); //Es portable. En cambio system("pause"); no funciona en GNU/Linux
    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++){
           if( (f[i][j]!=-1) && (f[i][j] != f[i][j-1]) ){ //Evita los -1, y no imprime los repetidos
            printf("%2d ", f[i][j]);
           }
        }
        printf("\n");
        for(j=0; j<ix[i]; j++)
            printf("   ");
        printf("|-> %d\n\n", ix[i]);
    }
    printf("---\n\n\n");
    printf("\nPulse una tecla para continuar...\n");
    getchar();
}

// fin del código
Obtenido de «https://es.wikibooks.org/w/index.php?title=Simulación_de_algoritmos/Ordenamiento/Externo/Mezcla_Equilibrada&oldid=200986»