Algoritmo de Ordenamiento externo por Mezcla Equilibrada
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