La idea central de este método consiste en realizar las particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias de tamaño fijo previamente determinadas.
Luego realiza la fusión de las secuencias ordenadas, alternativamente sobre dos archivos aplicando estas acciones en forma repetida se lograra que el archivo original quede ordenado.
Para la realización de este proceso de ordenación se necesitarán cuatro archivos. El archivo original F y tres archivos auxiliares a los que se denominaran F1, F2 y F3. De estos archivos, dos serán considerados de entrada y dos de salida; esto, alternativamente, con el objeto de realizar la fusión-partición. El proceso termina cuando en la realización de una fusión-partición el segundo archivo quede vacío.
F: 09 75 14 68 29 17 31 25 04 05 13 18 72 46 61
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 F2: 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 F1:
10. Si B1=FALSO entonces Escribir R1 en F 11. {Fin del condicional del paso 10} 12. Si B2=FALSO entonces Escribir R2 en F 13. {Fin del condicional del paso 12} 14. Repetir (mientras no sea el fin de archivo de F1) Leer R1 de F1 Escribir R1 en F 15. {Fin del condicional del paso 14} 16. Repetir (mientras no sea el fin de archivo de F2) Leer R2 de F2 Escribir R2 en F 17. {Fin del condicional del paso 16}
Obsérvese que al realizar la tercera fusión-partición el segundo archivo queda vació, por lo que se puede afirmar que el archivo ya se encuentra ordenado.
Imagen:
Código:
APP Mezcla Equilibrada.cpp:
#include<iostream>
using namespace std;
#include"gotoxy.h"
#include"Clase_Mezcla_Equilibrada.h"
#include"Menu_Mezcla_Equilibrada.h"
int main(){
Menu_Mezcla_Equilibrada();
return 0;
}
Clase_Mezcla_Equilibrada.h:
#include<fstream> //Libreria para los ficheros
class MezclaEquilibrada{
private:
char nombre[20];
//-- Metodos de los ficheros --//
void abrir(fstream *f, char nom[], int tip=1);
void cerrar(fstream *f);
//-- Metodos auxiliares de ordenar --//
void particionInicial();
void particionFusion();
void intercalacionDeArchivo(char nom1[], char nom2[], char nom3[], char nom4[]);
public:
MezclaEquilibrada(){ strcpy(nombre,"datos.txt");}
//-- Metodos de los ficheros --//
void limpiar();
bool hayDatos(char nom[]);
void mostrar(char nom[]);
void insertar(int d, char nom[]);
//-- Metodo propio de la Mezcla Equilibrada --//
void ordenar();
};
//-- Metodos para los ficheros --//
void MezclaEquilibrada::abrir(fstream *f, char nom[], int tip){
if(tip==1) //LECTURA
(*f).open(nom, ios::in );//->
//MODO TEXTO (Acceder a los datos) usaré ">>"
else if(tip==2) //ESCRITURA SIN BORRAR
(*f).open(nom, ios::out | ios::app); //->
//MODO TEXTO (Colocar datos y no borrará) usaré "<<"
else //ESCRITURA y BORRAR
(*f).open(nom, ios::out); //->
//MODO TEXTO (Colocar datos) usaré "<<"
}
void MezclaEquilibrada::cerrar(fstream *f){
(*f).close();
}
void MezclaEquilibrada::limpiar(){
fstream F, F1, F2;
abrir(&F, nombre, 3);
abrir(&F1, "F1.txt" , 3);
abrir(&F2, "F2.txt" , 3);
cerrar(&F);
cerrar(&F1);
cerrar(&F2);
}
bool MezclaEquilibrada::hayDatos(char nom[]){
fstream F;
abrir(&F, nom,1);
int x=-10001;
F>>x;
if(x!=-10001)
return true;
else
return false;
cerrar(&F);
}
void MezclaEquilibrada::mostrar(char nom[]){
fstream F;
abrir(&F, nom,1);
int dato;
F>>dato;
while(!F.eof()){
cout<<dato<<" ";
F>>dato;
}
cerrar(&F);
}
void MezclaEquilibrada::insertar(int d, char nom[]){
fstream F;
abrir(&F, nom, 2);
F<<d<<" ";
cerrar(&F);
}
//-- Metodos propias de la Mezcla Equilibrada --//
void MezclaEquilibrada::ordenar(){
particionInicial();
particionFusion();
}
void MezclaEquilibrada::particionInicial(){
int aux, dato; bool ban=true;
fstream F, F2, F3;
abrir(&F , nombre, 1);
abrir(&F2, "F2.txt", 3);
abrir(&F3, "F3.txt", 3);
F>>aux;
while(!F.eof() && !F.fail()){
F>>dato;
if(ban){
F2<<aux<<" ";
if(aux > dato)
ban=false;
}else{
F3<<aux<<" ";
if(aux > dato)
ban=true;
}
aux=dato;
}
cerrar(&F);
cerrar(&F2);
cerrar(&F3);
}
void MezclaEquilibrada::particionFusion(){
fstream F1;
abrir(&F1, "F1.txt", 1);
int con=0;
bool bandera=true;
do{
//con++;
if(bandera){
bandera=false;
intercalacionDeArchivo("F2.txt","F3.txt", nombre,"F1.txt");
}else{
bandera=true;
intercalacionDeArchivo(nombre ,"F1.txt","F2.txt","F3.txt");
}
F1>>con;
}while(!F1.eof());
cerrar(&F1);
// Ya esta ordenado
}
void MezclaEquilibrada::intercalacionDeArchivo(char nom1[], char nom2[], char nom3[], char nom4[]){
int aux1, aux2, dato ;
int mayor1, mayor2;
bool bandera1, bandera2=true;
fstream F1, F2, F3, F4;
abrir(&F1, nom1, 1);
abrir(&F2, nom2, 1);
abrir(&F3, nom3, 3);
abrir(&F4, nom4, 3);
//-- Conseguir los primeros numeros --//
F1>>aux1;
F2>>aux2;
//-- Asignar los mayores --//
//(Debe estar ya validados los ficheros que contengan al menos un dato.
mayor1=aux1;
mayor2=aux2;
//-- Escribir en orden cuando los dos tengan datos.
//-- Pero simultaneado los archivos.
while(!F1.eof() && !F2.eof()){
//-- Cambio de fichero para la Escritura --//
if(aux2 < mayor2 && aux1 < mayor1){
if(bandera2)
bandera2=false;
else
bandera2=true;
mayor1=aux1;
mayor2=aux2;
}
//----------------------------------------//
//-- Cambio de fichero para Lectura ------//
if((aux1 <= aux2 && aux1 >= mayor1) || aux2 < mayor2){
bandera1=true;
mayor1=dato=aux1;
}else{
bandera1=false;
mayor2=dato=aux2;
}
//---------------------------------------//
//-- Leer el dato en el fichero tal --//
if(bandera1)
F1>>aux1;
else
F2>>aux2;
//-------------------------------------//
//-- Escribir el dato en el fichero tal --//
if(bandera2)
F3<<dato<<" ";
else
F4<<dato<<" ";
//----------------------------------------//
}
//-- Escribir lo sobrante.
if(!F1.eof()){
while(!F1.eof()){
//-- Cambio de fichero para la Escritura --//
if(aux1 < mayor1){
if(bandera2)
bandera2=false;
else
bandera2=true;
}
mayor1=aux1;
//---------------------------------------//
//-- Escribir el dato en el fichero tal --//
if(bandera2)
F3<<aux1<<" ";
else
F4<<aux1<<" ";
F1>>aux1;
//---------------------------------------//
}
}else if(!F2.eof()){
while(!F2.eof()){
//-- Cambio de fichero para la Escritura --//
if(aux2 < mayor2){
if(bandera2)
bandera2=false;
else
bandera2=true;
}
mayor2=aux2;
//---------------------------------------//
//-- Escribir el dato en el fichero tal --//
if(bandera2)
F3<<aux2<<" ";
else
F4<<aux2<<" ";
F2>>aux2;
//---------------------------------------//
}
}
cerrar(&F1);
cerrar(&F2);
cerrar(&F3);
cerrar(&F4);
}
Menu_Mezcla_Equilibrada.h:
void Menu_Mezcla_Equilibrada(){
MezclaEquilibrada A;
char *z[1];
char *principal[5]={"MENU METODO DE MEZCLA EQUILIBRADA:",
"INGRESAR DATOS.",
"ORDENAR LOS DATOS.",
"MOSTRAR LOS DATOS.",
"ATRAS"};
char *a[5]={"MENU METODO DE MEZCLA EQUILIBRADA (INGRESAR):",
"INGRESAR UN NUMERO.",
"INGRESAR VARIOS NUMEROS.",
"INGRESAR 5 NUMEROS ALEATORIOS.",
"ATRAS."};
int op1=1, op2, op3, N, dato;
A.limpiar(); srand(0);
do{
op1=construirMenu(principal, 5, op1 + 1);
switch(op1){
case 1:
op2=1;
do{
op2=construirMenu(a, 5, op2 + 1);
if(op2==1 || op2==2){ //UNO O VARIOS DATOS.
N=1;
while(op2==2 && (N<=1 || N>=1000)){
z[0]="Digite cuantos datos desea ingresar:";
construirMenu(z,1);
cin>>N;
}
for(int i=0; i<N ; i++){
do{
z[0]="Digite un dato para colocarlo:";
construirMenu(z,1);
cin>>dato;
}while(dato<-10000 || dato>10000);
A.insertar(dato, "datos.txt");
z[0]="Se ha colocado el dato.";
construirMenu(z,1);
system("pause>>NULL");
}
}else if(op2==3){ //DATOS ALEATORIOS.
int RND;
z[0]="Se han colocado los datos aleatorios.";
construirMenu(z,1);
for(int i=0; i<5 ; i++){
do{
RND=rand() % 1000 - 250;
}while(RND<-1000 || RND>1000);
cout<<RND<<" ";
A.insertar(RND,"datos.txt");
}
system("pause>>NULL");
}
}while(op2!=4);
break;
case 2:
if(A.hayDatos("datos.txt")){//Si hay datos.
z[0]="Se ha ordenado el ficheros.";
A.ordenar();
}else
z[0]="No hay datos en el fichero.";
construirMenu(z,1);
system("pause>>NULL");
break;
case 3:
if(A.hayDatos("datos.txt")){//Si hay datos.
z[0]="Los datos son: ";
construirMenu(z,1);
A.mostrar("datos.txt");
}else{
z[0]="No hay datos en el fichero.";
construirMenu(z,1);
}
system("pause>>NULL");
break;
}
}while(op1!=4);
}
gotoxy.h:
#include<iostream>
#include<cstdlib>
#include<conio.h>
#include<windows.h>
using namespace std;
void limpiar(){
system("cls");
fflush(stdin);
cin.clear();
}
void texcolor(int x){
SetConsoleTextAttribute(GetStdHandle (STD_OUTPUT_HANDLE),x);
}
void gotoxy(int x, int y) {
COORD Cursor_Pos = {x,y};
SetConsoleCursorPosition(GetStdHandle (STD_OUTPUT_HANDLE), Cursor_Pos);
}
int construirMenu(char *opciones[], int can, int seleccion=2, int X=15, int Y=3){
bool ban=true;
int i,lim, tecla, opc=seleccion;
limpiar();
do{
//-- Buscar la frase más larga --//
for(lim=i=0; i<can && ban; i++){
if(strlen(opciones[i])>lim)
lim=strlen(opciones[i]);
}
for(i=Y; i<=(can + Y + 1) && ban; i++){
gotoxy(X, i);
//-- Esquinas y lineas verticales del lado izquierdo. --//
if(i==Y) cout<<"É";
else if(i!=can + Y + 1) cout<<"º";
else cout<<"È";
//-- Lineas horizontales y las opciones.--//
if(i==Y || i==can + Y + 1){
for(int j=0; j<lim + 6; j++) cout<<"Í";
}else{
//-- Cambio de Color --//
if(opc==i- Y)
texcolor(4);
//-- Las letras --//
if(i- (Y + 1) == 0)
gotoxy(X + 1 +(lim + 1 - strlen(opciones[i- (Y + 1)]))/2,i); // Centrado
else
gotoxy(X + 1, i);
cout<<" "<<opciones[i- (Y + 1)];
texcolor(7);
}
//-- Esquinas y lineas verticales del lado derecho. --//
gotoxy(X + lim + 6 + 1, i);
if(i==Y) cout<<"»";
else if(i!=can + Y + 1) cout<<"º";
else cout<<"¼";
}
//-- Funciones de reconocer las teclas --//
if(can==1){
gotoxy(X, i);
return 0;
}else
tecla = getch();
if(tecla==72){
if(opc!=2)//-- Flecha Arriba del teclado
opc--;
else
opc=can;
ban=true;
}else if(tecla==80){//-- Flecha Abajo del teclado
if(opc!=can)
opc++;
else
opc=2;
ban=true;
}else
ban=false;
}while(tecla!=13);
return opc - 1;
}
Descarga el código fuente desde aquí.
No hay comentarios :
Publicar un comentario