El método de ordenación por mezcla directa es probablemente el más utilizado por su fácil comprensión.
La idea central de este algoritmo consiste en la realización sucesiva de una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada la partición es de longitud 1, y la fusión o mezcla produce secuencias ordenadas de longitud 2. En la segunda pasada la partición es de longitud 2, y la fusión o mezcla produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la secuencia de la secuencia para la partición sea mayor o igual que el número de elementos del archivo original.
Ejemplo:
Supóngase que se desea ordenar las claves del archivo F. para realizar tal actividad se utilizan dos archivos auxiliares a los que se les denominará. F1 y F2.
F: 09 75 14 68 29 17 31 25 04 05 13 18 72 46 61.
Primera pasada:
Partición en secuencias de longitud 1.
F1: 09’ 14’ 29’ 31’ 04’ 13’ 72’ 61’
F2: 75’ 68’ 17’ 25’ 05’ 18’ 46’
Fusión en secuencias de longitud dos:
F: 09 75’ 14 68’ 17 29’ 25 31’ 04 05’ 13 18’ 46 72’ 61’
Segunda pasada:
Partición de secuencia de longitud 2
F1: 09 75’ 17 29’ 04 05’ 46 72’
F2: 14 68’ 25 31’ 13 18’ 61’
Fusión en secuencias de longitud 4.
F: 09 14 68 75’ 17 25 29 31’ 04 05 13 18’ 46 61 72’
Tercera pasada.
Partición en secuencia de longitud 4.
F1: 09 14 68 75’ 04 05 13 18’
F2: 17 25 29 31’ 46 61 72’
Fusión en secuencias de longitud 8
F: 09 14 17 25 29 31 68 75’ 04 05 13 18 46 61 72’
Cuarta pasada.
Partición en secuencia de longitud 8
F1: 09 14 17 25 29 31 68 75’
F2: 04 05 13 18 46 61 72’
Fusión en secuencias de longitud 16
F: 04 05 09 13 14 17 18 25 29 31 46 61 68 72 75
Imagen:
Código:
APP Mezcla Directa.cpp:
#include<iostream>
using namespace std;
#include"gotoxy.h"
#include"Clase_Mezcla_Directa.h"
#include"Menu_Mezcla_Directa.h"
int main(){
Menu_Mezcla_Directa();
return 0;
}
Clase_Mezcla_Directa.h:
#include<fstream> //Libreria para los ficheros
class MezclaDirecta{
private:
int N;
//-- Metodos de los ficheros --//
void abrir(fstream *f, char nom[], int tip=1);
void cerrar(fstream *f);
//-- Metodos de auxiliares de la ordenación --//
void particiona(int longitud);
void fusiona(int longitud);
public:
MezclaDirecta(){N=0;}
//-- Metodos de los ficheros --//
void limpiar();
bool hayDatos(char nom[]);
void mostrar(char nom[]);
void insertar(int d, char nom[]);
//-- Metodo de ordenacion --//
void ordenar();
};
//-- Metodos para los ficheros --//
void MezclaDirecta::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 MezclaDirecta::cerrar(fstream *f){
(*f).close();
}
void MezclaDirecta::limpiar(){
fstream F, F1, F2;
abrir(&F, "datos.txt", 3);
abrir(&F1, "F1.txt" , 3);
abrir(&F2, "F2.txt" , 3);
cerrar(&F);
cerrar(&F1);
cerrar(&F2);
}
bool MezclaDirecta::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 MezclaDirecta::mostrar(char nom[]){
fstream F;
abrir(&F, nom,1);
int dato;
F>>dato;
while(!F.eof()){
cout<<dato<<" ";
F>>dato;
}
cerrar(&F);
}
void MezclaDirecta::insertar(int d, char nom[]){
fstream F;
abrir(&F, nom, 2);
N++;
F<<d<<" ";
cerrar(&F);
}
//-- Metodo propio de Intercalación de Archivo --//
void MezclaDirecta::ordenar(){
int longitud=1;
while( longitud < N){
particiona(longitud);
fusiona(longitud);
longitud*=2;
}
}
void MezclaDirecta::particiona(int longitud){
fstream F, F1, F2;
int con1, con2 , dato;
abrir(&F, "datos.txt",1);
abrir(&F1, "F1.txt" ,3);
abrir(&F2, "F2.txt" ,3);
while(!F.eof()){
con1=0;
while(con1< longitud && !F.eof()){
F>>dato;
if(!F.eof())
F1<<dato<<" ";
con1++;
}
con2=0;
while(con2< longitud && !F.eof()){
F>>dato;
if(!F.eof())
F2<<dato<<" ";
con2++;
}
}
cerrar(&F);
cerrar(&F1);
cerrar(&F2);
}
void MezclaDirecta::fusiona(int longitud){
fstream F, F1, F2;
int con1, con2 , dato1, dato2;
bool ban1, ban2;
abrir(&F , "datos.txt",3);
abrir(&F1, "F1.txt" ,1);
abrir(&F2, "F2.txt" ,1);
ban1=ban2=true;
if(!F1.eof()){
F1>>dato1;
ban1=false;
}
if(!F2.eof()){
F2>>dato2;
ban2=false;
}
while( (!F1.eof() || ban1== false)
&& (!F2.eof() || ban2== false))
{
con1=con2=0;
while( (con1< longitud && ban1 ==false)
&& (con2< longitud && ban2 ==false))
{
if( dato1 <= dato2){
ban1=true;
con1++;
if(!F1.eof()){
F<<dato1<<" ";//Cambio
F1>>dato1;
ban1=false;
}
}else{
ban2=true;
con2++;
if(!F2.eof()){
F<<dato2<<" ";//Cambio
F2>>dato2;
ban2=false;
}
}
}// Fin del segundo while
if( con1 < longitud){
while( con1 < longitud && ban1==false){
ban1=true;
con1++;
if(!F1.eof()){
F<<dato1<<" ";//Cambio
F1>>dato1;
ban1=false;
}
}
}
if( con2 < longitud){
while( con2 < longitud && ban2==false){
ban2=true;
con2++;
if(!F2.eof()){
F<<dato2<<" ";//Cambio
F2>>dato2;
ban2=false;
}
}
}
}//fin del primer while
//Cambios
while(!F1.eof()){
F1>>dato1;
if(!F1.eof())
F<<dato1<<" ";
}
while(!F2.eof()){
F2>>dato2;
if(!F2.eof())
F<<dato2<<" ";
}
cerrar(&F);
cerrar(&F1);
cerrar(&F2);
}
Menu_Mezcla_Directa.h:
void Menu_Mezcla_Directa(){
MezclaDirecta A;
char *z[1];
char *principal[5]={"MENU METODO DE MEZCLA DIRECTA:",
"INGRESAR DATOS.",
"ORDENAR LOS DATOS.",
"MOSTRAR LOS DATOS.",
"ATRAS"};
char *a[5]={"MENU METODO DE MEZCLA DIRECTA (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