Mostrando entradas con la etiqueta ordenacion externa. Mostrar todas las entradas
Mostrando entradas con la etiqueta ordenacion externa. Mostrar todas las entradas

viernes, 3 de enero de 2014

Ordenación Externa: Mezcla Equilibrada en C++

Mezcla Equilibrada.

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.

Ordenación Externa: Mezcla Directa

Mezcla Directa.

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

jueves, 2 de enero de 2014

Ordenación Externa: Intercalación de Archivos en C++

Intercalación de archivos.

Por intercalación de archivos se entiende la unión de dos o más archivos ordenados de acuerdo con un campo clave en un solo archivo.

Ejemplo: se tienen dos archivos F1, F2 ordenados de acuerdo a un capo clave.

F1: 06 09 18 20 35

F2: 10 16 25 28 66 82 87

Debe producirse entonces un archivo F3 ordenado como resultado de la mezcla de F1 y F2. Solo pueden ser accedidas directamente dos claves la primera del archivo F1 y la segunda del archivo F2.

Las comparaciones que se realizan para producir el archivo F3 son las siguientes.

(06 < 10) , si se cumple la condición se escribe 06 en el archivo de salida F3, y se vuelve a leer otra clave de F1 (09)

(09 <10), si se cumple la condición se escribe 09 en el archivo F3 y se vuelve a leer otra clave de F1 (18)

(18<10), no se cumple la condición , se escribe 10 en el archivo de salida F3 y se vuelve a leer otra clave de F2,

El estado de los archivos F1, F2 Y F3 hasta el momento es el siguiente.

F1: 06 09 18 20 35

F2: 10 16 25 28 66 82 87

F3: 06 09 10

El proceso continúa hasta que en uno u otro archivo se detecte el fin de archivo, en tal caso solo se tendrán que trascribir las claves del archivo no vacío al archivo de salida F3. Este es el resultado final de la intercalación de F1 y F2

F3: 06 09 10 16 18 20 25 28 35 66 82 87.



Imagen:





Código:

APP Intercalación De Archivo.cpp:
#include<iostream>
using namespace std;

#include"gotoxy.h"
#include"Clase_Intercalacion_De_Archivo.h"
#include"Menu_Intercalación_De_Archivo.h"

int main(){
	Menu_Intercalacion_De_Archivo();
	return 0;
}

Clase_Intercalacion_De_Archivo.h:
#include<fstream> //Libreria para los ficheros

class Intercalacion{
private:
	void abrir(fstream *f, char nom[], int tip=1);
	void cerrar(fstream *f);
public:
	void limpiar();
	bool hayDatos(char nom[]);
	void mostrar(char nom[]);
	void insertar(int d, char nom[]);
	void ordenar();
};
//-- Metodos para los ficheros --//
void Intercalacion::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 Intercalacion::cerrar(fstream *f){
	(*f).close();
}
void Intercalacion::limpiar(){
  fstream F1, F2, F3;
	abrir(&F1, "F1.txt", 3);
	abrir(&F2, "F2.txt", 3);
	abrir(&F3, "F3.txt", 3);
	cerrar(&F1);
	cerrar(&F2);
	cerrar(&F3);
}
bool Intercalacion::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 Intercalacion::mostrar(char nom[]){
	fstream F;
	abrir(&F, nom,1);
	int dato;
	F>>dato;
	while(!F.eof()){
		cout<<dato<<" ";
	  F>>dato;
	}
	cerrar(&F);
}
void Intercalacion::insertar(int d, char nom[]){
	fstream F;
	abrir(&F, nom, 2);
	F<<d<<" ";
	cerrar(&F);
}
//-- Metodo propio de Intercalación de Archivo --//
void Intercalacion::ordenar(){
	fstream F1, F2, F3;
	abrir(&F1, "F1.txt",1);
	abrir(&F2, "F2.txt",1);
	abrir(&F3, "F3.txt",3);

	int  r1, r2;
	F1>>r1;
	F2>>r2;
	//-- Escribir en orden cuando los dos tengan datos.
	while(!F1.eof() && !F2.eof())
	  if(r1 < r2){
	    F3<<r1<<" ";
			F1>>r1;
	  }
	  else{
			F3<<r2<<" ";
		  F2>>r2;
	  }
  //-- Escribir lo sobrante.
	if(!F1.eof())
		while(!F1.eof()){
		  F3<<r1<<" ";
		  F1>>r1;
	  }
	else if(!F2.eof())
		while(!F2.eof()){
		  F2<<r2<<" ";
		  F2>>r2;
		}
	cerrar(&F1);
	cerrar(&F2);
	cerrar(&F3);
}

Menu_Intercalación_De_Archivo.h
void Menu_Intercalacion_De_Archivo(){
	Intercalacion A;
	char *z[1];
	char *principal[5]={"MENU METODO DE INTERCALACION DE ARCHIVO:",
											"INGRESAR DATOS A UN FICHERO.",
											"ORDENAR LOS DATOS.",
											"MOSTRAR LOS DATOS DE UN FICHERO.",
											"ATRAS"};
	char *a[4]={"MENU METODO DE INTERCALACION DE ARCHIVO (INGRESAR):", 
							"INGRESAR UN NUMERO.",
							"INGRESAR VARIOS NUMEROS.",
							"ATRAS."};
	char *b[4]={"MENU METODO DE INTERCALACION DE ARCHIVO: ",
						 "FICHERO 1.",
						 "FICHERO 2.",
						 "FICHERO 3."};

	int op1=1, op2, op3, N, dato, mayor1, mayor2;
	char nomFic[7];
	mayor1=mayor2= -1001;
	A.limpiar();
	do{
		op1=construirMenu(principal, 5, op1 + 1);
		switch(op1){
			case 1: 
				op2=1;
				do{
					op2=construirMenu(a, 4, op2 + 1);
					if(op2!=3){
						op3=construirMenu(b, 3);
						if(op3==1)
							strcpy(nomFic,"F1.txt");
						else
							strcpy(nomFic,"F2.txt");
					}
					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;
								if(op3==1 && dato > mayor1)
									mayor1=dato;
								else if(op3==2 && dato > mayor2)
									mayor2=dato;
								else{
									z[0]="El dato debe ser mayor.";
									construirMenu(z,1);
									system("pause>>NULL");
									dato=-10001;
								}
							}while(dato<-10000 || dato>10000);
							A.insertar(dato, nomFic);
							z[0]="Se ha colocado el dato.";
							construirMenu(z,1);
							system("pause>>NULL");
						}
					}
				}while(op2!=3);
				break;
			case 2:
				if(A.hayDatos("F1.txt") && A.hayDatos("F2.txt")){//Si hay datos.
					z[0]="Se ha ordenado los ficheros y se ha guardado en el fichero 3.";
					A.ordenar();
				}else if(!A.hayDatos("F1.txt"))
					z[0]="El fichero 1 no se ha ingresado al menos un dato.";
				else
					z[0]="El fichero 2 no se ha ingresado al menos un dato.";
				construirMenu(z,1);
			  system("pause>>NULL");
				break;
			case 3:
				op3=construirMenu(b, 4);
				if(op3==1)
					strcpy(nomFic,"F1.txt");
				else if(op3==2)
					strcpy(nomFic,"F2.txt");
				else
					strcpy(nomFic,"F3.txt");
				if(A.hayDatos(nomFic)){//Si hay datos.
					z[0]="Los datos son: ";
					construirMenu(z,1);
					A.mostrar(nomFic);
				}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í.