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í.

Método de Ordenación Radix en C++

Hola amig@s para terminar la entrega de Métodos de ordenación lo haremos con el método Radix. En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.

La mayor parte de los ordenadores digitales representan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente. Existen dos clasificaciones de radix sort: el de dígito menos significativo (LSD) y el de dígito más significativo (MSD). Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo. Radix sort MSD trabaja en sentido contrario.

Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos. Radix sort LSD usa típicamente el siguiente orden: claves cortas aparecen antes que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija. Una secuencia como "b, c, d, e, f, g, h, i, j, ba" será ordenada léxicamente como "b, ba, c, d, e, f, g, h, i, j". Si se usa orden léxico para ordenar representaciones de enteros de longitud variable, entonces la ordenación de las representaciones de los números del 1 al 10 será "1, 10, 2, 3, 4, 5, 6, 7, 8, 9", como si las claves más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con espacios en blanco, para hacerlas tan largas como la clave más larga, para el propósito de este ordenamiento.

Imagen:

Código:

RadixSort.cpp:

#include "RadixSort.h"
void main(){
 RadixSort RS;
 RS.inicia();
}

RadixSort.h:

#include <iostream>
#include <windows.h>
#include <math.h>
using namespace std;
#define MAX 100

struct{
 int inf;
 int sig;
}nodo[MAX];

class RadixSort{
public:
 int vector[MAX], post[MAX],frente[MAX];
 void inicia(void);
 void radixSort(int[] ,int);
};

void RadixSort::inicia(){
 int n;
 cout<<"Ingrese el numeo de elementos que desea insertar: ";cin>>n;
 for(int i=0;i<n;i++){
  cout<<endl<<"Elemento["<<i+1<<"]: ";cin>>vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Elementos desordenados:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<endl<<vector[i];
 }
 radixSort(vector,n);
 cout<<endl<<endl<<"Elementos ordenados por metodo Radix Sort:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<endl<<vector[i];
 }
 system("pause>null");
}

void RadixSort::radixSort(int V[], int N){
 int exp, primero, p, q, y,j,i,k;
 for (int i = 0; i < N-1; i++) {
  nodo[i].inf = V[i];
  nodo[i].sig = i+1;
 }
 nodo[N-1].inf = V[N-1];
 nodo[N-1].sig = -1;
 primero = 0;
 for ( k = 1; k < 5; k++) {
  for ( i = 0; i < 10; i++) {
   post[i] = -1;
   frente[i] = -1;
  }

  while (primero != -1) {
   p = primero;
   primero = nodo[primero].sig;
   y = nodo[p].inf;
   exp = pow((double)10, k-1);
   j = (y/exp) % 10;
   q = post[j];
   if (q == -1)
    frente[j] = p;
   else
    nodo[q].sig = p;
   post[j] = p;
  }

  for (j = 0; j < 10 && frente[j] == -1; j++);
  ;//no hacemos nada unicamente nos desplazamos x el vector hasta q salga del ciclo
  primero = frente[j];
  while (j <= 9) {
   for ( i = j+1; i < 10 && frente[i] == -1; i++);
   ;//no hacemos nada unicamente nos desplazamos x el vector hasta q salga del ciclo
   if (i <= 9){
    p = i;
    nodo[post[j]].sig = frente[i];
   }
   j = i;
  }
  nodo[post[p]].sig = -1;
 }
 for ( i = 0; i < N; i++) {
  V[i] = nodo[primero].inf;
  primero = nodo[primero].sig;
 }
}

Descarga el código desde aquí.

Metódo de Ordenación Comb Sort en C++

Hola amig@s continuando con la entrega de los metodós de ordenación esta vez es el turno de el metodo de Comb Sort este metódo en ciencias de la computación, el comb sort (comb=peine) es un algoritmo de ordenamiento relativamente simple diseñado por Wlodzimierz Dobosiewicz en 1980. Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo publicado por la revista Byte en abril de 1991. El algoritmo comb sort mejora el algoritmo de ordenamiento de burbuja y rivaliza en velocidad con algoritmos más complejos como el Quicksort. La idea básica es eliminar tortugas, o pequeños valores cerca del final de la lista, ya que en el algoritmo de ordenamiento de burbuja esto reduce la velocidad de ordenamiento tremendamente. (Los conejos, grandes valores alrededor del inicio de la lista, no plantean un problema en el algoritmo de ordenamiento de burbuja.)
En el ordenamiento de burbuja, cuando dos elementos cualquiera se comparan, siempre tienen un espacio (distancia entre ellos) de 1. La idea básica del algoritmo comb sort es que el espacio pueda ser mucho mayor de uno. El ordenamiento Shell también se basa en esta idea, pero es una modificación del algoritmo de ordenamiento por inserción más que del algoritmo de ordenamiento de burbuja.
El espacio se inicia como la longitud de la lista a ordenar dividida por el factor de encogimiento (generalmente 1,3 o 1.3), y la lista se ordena con este valor (redondeado a la baja a un entero si es necesario) para el espacio. Después el espacio se divide por el factor de encogimiento de nuevo, la lista se ordena con este nuevo espacio, y el proceso se repite hasta que el espacio es 1. En este momento, el algoritmo comb sort continua usando un espacio de 1 hasta que la lista está completamente ordenada. La etapa final del ordenamiento es así equivalente al algoritmo de ordenamiento de burbuja, pero en este momento la mayoría de las tortugas ya han sido tratadas, de manera que un algoritmo de ordenamiento de burbuja será eficiente.

Imagen:

Código:

CombSort.cpp:

#include "CombSort.h"
void main(){
 CombSort CS;
 int n;
 do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100);
 for(int i=0;i<n;i++){
  cout<<endl<<"Dato["<<i+1<<"]: ";cin>>CS.Vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Vector original:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<CS.Vector[i]<<" ";
 }
 CS.combSort(CS.Vector,n);
 cout<<endl<<endl<<"Vector Ordenado Con El Metodo Comb Sort :"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<CS.Vector[i]<<" ";
 }
 system("pause>null");
}

CombSort.h:

#include <iostream>
#include <windows.h>
using namespace std;
class CombSort{
public:
 int Vector[100];
 void combSort(int[], int );
};
void CombSort::combSort(int v[], int N){
    const float reducir = 1.3f;
    int aux;
    int i, brecha = N;
    bool intercambiado = false;
 
    while ((brecha > 1) || intercambiado) {
        if (brecha > 1) {
            brecha = (int)((float)brecha / reducir);
        }
 
        intercambiado = false;
 
        for (i = 0; brecha + i < N; ++i) {
            if (v[i] - v[i + brecha] > 0) {
                aux = v[i];
                v[i] = v[i + brecha];
                v[i + brecha] = aux;
                intercambiado = true;
            }
        }
    }
}

descarga el código fuente desde aquí.

Metodo de Ordenacion Shaker Sort en C++

Hola amig@s en esta ocasión y continuando con los métodos de ordenación les mostare el Shaker sort es también, y mejor, conocido como Cocktail Sort y en castellano como Burbuja Didireccional o Sacudida es la mejora del método de burbuja en el que el proceso se realiza desde la primera posición a la última de la disposición en la dirección opuesta, impidiendo así artículos más pequeños se lleva más tiempo para "subir" a las primeras posiciones.

Imagen:

Código:

ShakerSort.cpp:

#include "ShakerSort.h"
void main(){
 ShakerSort SK;
 int n;
 do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100);
 for(int i=0;i<n;i++){
  cout<<endl<<"Dato["<<i+1<<"]: ";cin>>SK.vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Vector original:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<SK.vector[i]<<" ";
 }
 SK.shakerSort(SK.vector,n);
 cout<<endl<<endl<<"Vector Ordenado Con El Metodo Shaker Sort (Sacudida):"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<SK.vector[i]<<" ";
 }
 system("pause>null");
}

ShakerSort.h:

#include <iostream>
#include <windows.h>
using namespace std;
class ShakerSort{
public:
 int vector[100];
 void shakerSort(int[] ,int );
};
void ShakerSort::shakerSort(int v[],int N){
 int i = 0 , izq = 1 , der = N-1 , k = N-1 , aux = 0;
 while( der >= izq ){      
  for( i = der ; i>= izq ; i-- )          
   if( v[i-1] > v[i]){
    aux = v[i-1];      
    v[i-1]=v[i];
    v[i]=aux;
    k=i;
   }
   izq = k + 1;
   for( i = izq ; i <= der ; i++)
    if( v[i-1] > v[i] ){
     aux = v[i-1];
     v[i-1]=v[i];
     v[i]=aux;
     k=i;
   }
    der = k-1;
 }
}

Descarga el código fuente desde aquí.