Unidad 7: Ordenamientos Externos
Introducción:
En esta Unidad explicaremos 2 algoritmos para el Ordenamiento de Archivos. A continuación mencionaremos los diferentes métodos para ordenar:
Mezcla Directa
Definición:
Este algoritmo consiste en tener un archivo A desordenado. Este archivo se ordenara haciendo los siguientes pasos:
1.- Definir tamaño de tramo igual a 1
2.- Repartir el archivo A en dos archivos B y C escribiendo alternadamente un tramo en cada uno
3.- Aplicar el algoritmo de mezcla simple a cada par de tramos correspondiente de los archivos B y C guardando el resultado en el archivo A
4.- Duplicar el tamaño del tramo
5.- Regresar al paso 2 si el tamaño del tramo es menor que la cantidad de elementos a ordenar
Programa:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>
class Archivos
{
public:
void Mostrar(FILE *fich)
{
char linea[128];
rewind(fich);
fgets(linea, 128, fich);
while(!feof(fich))
{
puts(linea);
fgets(linea, 128, fich);
}
}
void Mezcla(FILE *fich)
{
int ordenado;
FILE *aux[2];
do
{
aux[0] = fopen("aux1.txt", "w+");
aux[1] = fopen("aux2.txt", "w+");
rewind(fich);
Separar(fich, aux);
rewind(aux[0]);
rewind(aux[1]);
rewind(fich);
ordenado = Mezclar(fich, aux);
fclose(aux[0]);
fclose(aux[1]);
}while(!ordenado);
remove("aux1.txt");
remove("aux2.txt");
}
void Separar(FILE *fich, FILE **aux)
{
char linea[128], anterior[2][128];
int salida = 0;
strcpy(anterior[0], "");
strcpy(anterior[1], "");
fgets(linea, 128, fich);
while(!feof(fich))
{
if(salida == 0 && strcmp(linea, anterior[0]) < 0)
salida = 1;
else if(salida == 1 && strcmp(linea, anterior[1]) < 0)
salida = 0;
strcpy(anterior[salida], linea);
fputs(linea, aux[salida]);
fgets(linea, 128, fich);
}
}
int Mezclar(FILE *fich, FILE **aux)
{
char ultima[128], linea[2][128], anterior[2][128];
int entrada;
int tramos = 0;
fgets(linea[0], 128, aux[0]);
fgets(linea[1], 128, aux[1]);
strcpy(ultima, "");
strcpy(anterior[0], "");
strcpy(anterior[1], "");
while(!feof(aux[0]) && !feof(aux[1]))
{
if(strcmp(linea[0], linea[1]) <= 0)
entrada = 0;
else
entrada = 1;
strcpy(anterior[entrada], linea[entrada]);
fputs(linea[entrada], fich);
fgets(linea[entrada], 128, aux[entrada]);
if(strcmp(anterior[entrada], linea[entrada]) >= 0)
{
if(!entrada)
entrada = 1;
else
entrada = 0;
tramos++;
do
{
strcpy(anterior[entrada], linea[entrada]);
fputs(linea[entrada], fich);
fgets(linea[entrada], 128, aux[entrada]);
}while(!feof(aux[entrada]) && strcmp(anterior[entrada], linea[entrada]) <= 0);
}
}
if(!feof(aux[0]))
tramos++;
while(!feof(aux[0]))
{
fputs(linea[0], fich);
fgets(linea[0], 128, aux[0]);
}
if(!feof(aux[1]))
tramos++;
while(!feof(aux[1]))
{
fputs(linea[1], fich);
fgets(linea[1], 128, aux[1]);
}
return(tramos == 1);
}
}tec;
main()
{
FILE *fichero;
int res,op=0,b=0;
while(op!=3)
{
clrscr();
cout<<"\n1) Recorrido Desordenado\n2) Recorrido Ordenado\n3) Salir"<<endl;
gotoxy(1,1);
cout<<"Que deseas hacer?: ";
cin>>op;
gotoxy(1,10);
fichero = fopen("mezcla.txt", "r+");
switch (op)
{
case 1:
if(b!=1)
{
b=1;
tec.Mostrar(fichero);
}
else
cout<<"El Archivo ya esta Ordenado..."<<endl;
break;
case 2:
tec.Mezcla(fichero);
tec.Mostrar(fichero);
break;
case 3:
cout<<"Salir..."<<endl;
break;
default:
cout<<"Opcion Erronea..."<<endl;
break;
}
fclose(fichero);
getch();
}
}
Mezcla Directa
Definición:
Es una mejora del algoritmo de mezcla directa puesto que en vez de considerar tramos de tamaño fijo se toman en cuenta para la ordenación en todo momento tramos de longitud máxima.
Al igual que el mezcla directa se debe hacer un proceso de partir el archivo original para mezclarlo, posteriormente mientras en el archivo C haya elementos a mezclar.
Programa:
#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#include <string.h>
void mezcla_directa(char *);
void mezclar(char *, int );
void partir(char *, int );
void mezcla_simple(char *,char *,char *);
void main(){
char n[10]="mezcla.txt";
mezcla_directa(n);
getch();
}
void mezcla_simple(char *A,char *B,char *C)
{
FILE *a,*b,*c;
int ra,rb;
a=fopen(A,"rb");
b=fopen(B,"rb");
c=fopen(C,"rb");
if(a&&b&&c)
{
fread(&ra,sizeof(ra),1,a);
fread(&rb,sizeof(rb),1,b);
while(!feof(a)&&!feof(b))
{
if(ra<=rb)
{
fwrite(&ra,sizeof(ra),1,c);
fread(&ra,sizeof(ra),1,a);
}
else
{
fwrite(&rb,sizeof(rb),1,c);
fread(&ra,sizeof(ra),1,b);
}
}
while(!feof(a))
{
fwrite(&ra,sizeof(ra),1,c);
fread(&ra,sizeof(ra),1,a);
}
while(!feof(a))
{
fwrite(&rb,sizeof(rb),1,c);
fread(&rb,sizeof(rb),1,b);
}
fclose(a);
fclose(b);
fclose(c);
}
}
void mezcla_directa(char *nom){
int t=1, n=5;
FILE *a,*b,*c;
a=fopen(nom,"r+");
b=fopen("m1.txt","r+");
c=fopen("m2.txt","r+");
while(t<n){
partir(nom,t);
mezcla_simple("m1.txt","m2.txt",nom);
mezclar(nom,t);
t = t* 2;
}
}
void partir(char *nom, int t){
FILE *a,*b,*c;
int reg, cont, sw=1;
a=fopen(nom,"r+");
b=fopen("m1.txt","a+");
c=fopen("m2.txt","a+");
if(a&&b&&c){
fread(®,sizeof(reg),1,a);
while(!feof(a)){
for(cont=0;cont<t && !feof(a);cont++){
if(sw)
fwrite(®,sizeof(reg),1,b);
else
fwrite(®,sizeof(reg),1,c);
fread(®,sizeof(reg),1,a);
}
sw=!sw ;
}
}
fclose(a);
fclose(b);
fclose(c);
}
void mezclar(char *nom, int t){
FILE *a,*b,*c;
int rb,rc,ctb,ctc;
a= fopen(nom,"w+");
b= fopen("m1","r+");
c= fopen("m2","r+");
if(a&&b&&c){
fread(&rb,sizeof(rb),1,b);
fread(&rc,sizeof(rb),1,c);
while(!feof(b) && !feof(c)){
ctb=ctc=t;
while(ctb && ctc && !feof(b) && !feof(c)){
if(rb<rc){
fwrite(&rb,sizeof(rb),1,a);
fread(&rb,sizeof(rb),1,b);
ctb--;
}
else{
fwrite(&rc,sizeof(rc),1,a);
fread(&rc,sizeof(rc),1,c);
ctc--;
}
}
while(ctb && !feof(b)){
fwrite(&rb,sizeof(rb),1,a);
fread(&rb,sizeof(rb),1,b);
ctb--;
}
while(ctc && !feof(c)){
fwrite(&rc,sizeof(rc),1,a);
fread(&rc,sizeof(rc),1,c);
ctc--;
}
}
while(!feof(b)){
fwrite(&rb,sizeof(rb),1,a);
fread(&rb,sizeof(rb),1,b);
}
while(!feof(c)){
fwrite(&rc,sizeof(rc),1,a);
fread(&rc,sizeof(rc),1,c);
}
}
fclose(a);
fclose(b);
fclose(c);
remove("m1");
remove("m2");
}