Bibliografias

Los sitios utilizados fueron:

http://www.recursosdelweb.com

Universidad de valladolid
http://www.infor.uva.es

Universidad del Rey Juan Carlos
http://gavab.escet.urjc.es/

Enciclopedia Wikipedia
http://es.wikipedia.org/wiki/Portada

Algunos de los métodos obtenidos de los sitios mencionados fueron analizados e investigados en sitios varios para su mejor comprensión , análisis y confirmación de la información.

Algunas Conclusiones

Se compararon los métodos descriptos con distintas cantidades de registros en los vectores (pocos y muchos registros), dando resultados similares a lo manifestado en los gráficos adjuntos.

Podemos concluir que los métodos Shell Sort o Selección Directa son los mas eficientes en las pruebas que realizamos.

Desde el punto de vista de cantidades de lecturas Shell Sort es ampliamente mas eficiente que inserción, mientras que en cantidad de Intercambios Selección Directa debe realizar muchos mas intercambios que Shell Sort para poder ordenar un vector.

Esta tendencia se repito para lotes de entre 100 y 10.000 registros por vector.

En relacion a los metodos menos eficientes podemos mencionar que Burbuja E Insercion son los que mas lecturas deben realizar para ordenar un vector (Insercion incluso aproximadamente un 15% mas que burbuja)

En cuanto a la cantidad de Lecturas de estos ultimos dos metodos, Insercion realiza aproximadamente un 50 % mas.

Algunas Pruebas (Analisis de Intercambios)

Para pruebas de 100 lotes se obtuvieron los siguientes resultados en PROMEDIOS DE INTERCAMBIOS por metodo y segun la cantidad de registros.

Los metodos Burbuja, Isercion e Insort son los que mas Intercambios deben realizar para ordenar vectores, mientras que el Metodo de Seleccion directa y Shell Short son los que menos intercambios debe realizar (el primer metodo incluso es ligeramente inferior al segundo en cantidades de intercambios)

Si los analizamos con las cantidades de lecturas que realizan, Shell Short seria el mas eficiente en ambas relaciones.

En cantidades de intercambios tenemos los siguientes ejemplos

Graficamente lo podriamos representar:

Algunas Pruebas (Analisis de Lecturas)

Para pruebas de 100 lotes se obtuvieron los siguientes resultados en PROMEDIOS DE LECTURA por metodo y segun la cantidad de registros

Los metodos Burbuja y Seleccion directa son los que mas lecturs deben realizar para ordenar vectores, mientras que el que menos lleva a cabo es el metodo ShellSort.

Graficamente podemos mostrar:

Programa Ordena Vectores

Este es el codigo desarrollado para ordenar vectores por distintos metodos.

#include
#include // textcolor(); textbackground(); gotoxy()
#include
#include //Exit()
#include //memcpy

#define Separador ','
#define MAX_VALOR 10000 //Maximo valor Numerico (0 a MAX_VALOR) que puede tomar un campo del Vector.
#define MAX_REGIS 10000 //Cantidad de Posiciones del Vector.

int TOPE;
/*
Al Principio del desarrollo se definió el TOPE con un Define.
El TOPE indicaba la cantidad de registros del Vector.

Al avanzar el Desarrollo se implemento el Vector con MAX_VALOR posiciones,
y el TOPE (variable global) la cantidad de registros a Ordenar.

MAX_VALOR: Cantidad de Posiciones del Vector
TOPE : Cantidad con la que se trabaja.
*/

typedef int bool;
typedef char str10[11];
typedef char str20[21];
typedef int tyVec[MAX_REGIS];


struct sReg{
str20 Metodo ; //Nombre del Metodo
str10 LoteNro ; //Nro de Prueba (Ejemplo, 50 distintos Vec)
str10 CantReg ; //Cant. Reg. del Vector.
str10 CantLect; //Cant. de Lecturas, al ordenar
str10 CantSwap; //Cant. de Cambios , al ordenar
char Enter ; //Esta es para el CSV, arch. de salida.
};//fin struct sReg


struct sFile{FILE* Fil; sReg Reg;};
/*
Estructura que contiene el FILE y su Registro.
Esta implementación evita definir por Separado el FILE
de su respectiva estructura (Registro).
*/

// prototipos
// Se comentan los procedimientos en su interior.
void Bienvenido();
void AbrirLog(FILE * & F);
void CantReg_Lotes(int & TOPE, int & CantLotes);
void Proceso_Datos(int Loop, sFile & Files);
void CargoVec(tyVec Vec);
void Grabo_Log(sFile & Files);
void ArregloStr(char * str, int Tope, bool AddSepa);
void HastaLuego();


void Metodo1(sReg & Reg, tyVec Vec);
void Metodo2(sReg & Reg, tyVec Vec);
void Metodo3(sReg & Reg, tyVec Vec);
void Metodo4(sReg & Reg, tyVec Vec);
void Metodo5(sReg & Reg, tyVec Vec);
void a_char (unsigned long Lecturas, unsigned long Swap, str10 & CantLect, str10 & CantSwap);


void main() {
// Se definen Variables.
sFile Files;
int CantLotes;
int Loop;
// Procedimientos de Inicializacion
randomize();
Bienvenido();
AbrirLog(Files.Fil);
CantReg_Lotes(TOPE,CantLotes);
while(TOPE!=-1){ // Mientras (WHILE) el Usuario desee procesar datos (TOPE!=-1)
// Procesa datos para CantLotes
for(Loop=1;Loop<=CantLotes;Loop++) {
cout << "Procesando Lote Nro: " << Loop << endl;
itoa(Loop,Files.Reg.LoteNro,10);
Proceso_Datos(Loop, Files);
}
CantReg_Lotes(TOPE,CantLotes);
}
fclose(Files.Fil);
HastaLuego();
} // void main()


void Proceso_Datos(int Loop, sFile & Files){
/*
Se devine el Vector Madre, Vec,
y se le pasa a los Procedimientos una
copia, alojada en VecPaso.
*/
tyVec Vec;
tyVec VecPaso;
CargoVec(Vec);

memcpy (VecPaso,Vec,sizeof(VecPaso));
Metodo1(Files.Reg,VecPaso);
Grabo_Log(Files);

memcpy (VecPaso,Vec,sizeof(VecPaso));
Metodo2(Files.Reg,VecPaso);
Grabo_Log(Files);

memcpy (VecPaso,Vec,sizeof(VecPaso));
Metodo3(Files.Reg,VecPaso);
Grabo_Log(Files);

memcpy (VecPaso,Vec,sizeof(VecPaso));

Metodo4(Files.Reg,VecPaso);
Grabo_Log(Files);

memcpy (VecPaso,Vec,sizeof(VecPaso));
Metodo5(Files.Reg, VecPaso);
Grabo_Log(Files);
}

void Bienvenido() {
//Pantalla de Bienvenida
textcolor(WHITE);
textbackground(BLUE);
clrscr();
gotoxy(10,03);cout << "Taller II (1ero 2da) ";
gotoxy(10,10);cout << "Bienvenido al Sistema de Ordenamientos.";
gotoxy(10,12);cout << "Integrantes: ";
gotoxy(10,13);cout << " Bekerian Veronica ";
gotoxy(10,14);cout << " Herrero Alejandro ";
gotoxy(10,15);cout << " Bohlmann Martin ";
getch();
clrscr();
} // void Bienvenido();

void AbrirLog(FILE * & F) {
/*
Rutina de Apertura del File, modo Write Text.
No se utiliza el Append ya que nuestro Programa
Permite modificar los lotes de prueba.
*/
F = fopen("C:\\LOG.csv","wt");
if (! F) {
cout << "No se pudo abrir archivo para grabarlo!";
getch();
exit(0);
}
}

void CantReg_Lotes(int & TOPE, int & CantLotes){
//Solicita el Ingreso de la Cantidad de Registros a Evaluar
//y la cantidad de Lotes de Prueba
cout << "Ingrese Cantidad de Registros a Ordenar (2-" << MAX_REGIS << ";-1 Finalizar!): ";
do
cin >> TOPE;
while(TOPE != -1 && (TOPE < 2 || TOPE> MAX_REGIS));

if (TOPE!=-1) {
cout << "Ingrese Cantidad de Lotes que desea correr (1-100): ";
do
cin >> CantLotes;
while(CantLotes < 1 || CantLotes>100);
}
} //void CantReg_Lotes(int & TOPE, int & CantLotes);

void CargoVec(tyVec Vec){
//Carga Valores Aleatorios
int i;
for(i=0; i Vec[i] = rand() % MAX_VALOR;
}


void Grabo_Log(sFile & Files){
//GRABA CSV
ArregloStr(Files.Reg.Metodo ,sizeof(Files.Reg.Metodo) ,1);
ArregloStr(Files.Reg.LoteNro ,sizeof(Files.Reg.LoteNro) ,1);
ArregloStr(Files.Reg.CantLect,sizeof(Files.Reg.CantLect),1);
itoa(TOPE, Files.Reg.CantReg ,10);
ArregloStr(Files.Reg.CantReg ,sizeof(Files.Reg.CantReg) ,1);
ArregloStr(Files.Reg.CantSwap,sizeof(Files.Reg.CantSwap),0);
//
Files.Reg.Enter = (char)13;
fwrite(&Files.Reg, sizeof(sReg), 1, Files.Fil);
}

void ArregloStr(char * str, int Tope, bool AddSepa){
//En el CString, pasa Null´s a Espacios y
//el último byte el Separador del CSV.
int i=0;
int l;
while (i i++;

for (l=i;l str[l] = ' ';

if (AddSepa)
str[Tope-1] = Separador;

}

void HastaLuego() {
// Muestra Pantalla Salida
textcolor(GREEN);
textbackground(BLUE);
clrscr();
gotoxy(10,03);cout << "Taller II (1ero 2da) ";
gotoxy(10,10);cout << "Gracias por usar el Sistema. ";
gotoxy(10,12);cout << "Atte: ";
gotoxy(10,13);cout << " Bekerian Veronica ";
gotoxy(10,14);cout << " Herrero Alejandro ";
gotoxy(10,15);cout << " Bohlmann Martin ";
getch();
} // void HastaLuego();







/* RUTINAS DE ORDENAMIENTO */


void Metodo1(sReg & Reg, tyVec Vec){ //"metodo de burbuja"
/*****************************************************************************
funcion:Este algoritmo compara elementos consecutivos del arreglo uno con
respecto delotro, si es mayor o menor según el tipo de ordenamiento y los
cambia de posicion. Este proceso se repite recorriendo todo el arreglo para
posicionar un solo dato, por lo que es necesario repetirlo para los demas
datos del arreglo.Su implementacion es la siguiente:
******************************************************************************/
strcpy(Reg.Metodo,"Burbuja");
unsigned long CantLect=0; // Cantidad de Lecturas
unsigned long CantSwap=0; // Cantidad de Intercamvios
int i,j; // variable para el for
int m; // auxiliar utilizado

for(i=0;i for(j=i+1;j CantLect++;
if(Vec[i]>Vec[j]){ //compara si el valor leido es mayor al anterior.
m=Vec[i]; //si es mayor lo guarda en una variable aux
Vec[i]=Vec[j]; //intercambia los datos
Vec[j]=m; //iden anterior
CantSwap++;
}
}
}
a_char (CantLect, CantSwap, Reg.CantLect, Reg.CantSwap);//cambia int a string
} //fin del void metodo1

void Metodo2 (sReg & Reg, tyVec Vec){ //"metodo de insercion"

/*****************************************************************************
funcion: como a las cartas se toma la primer carta y la coloco en mi mano.
Luego tomo la segunda y la comparo con la que tengo: si es mayor, la pongo
a la derecha, y si es menor a la izquierda . Despues tomo la tercera y la
comparo con las que tengo en la mano, desplazándola hasta que quede en su
posicion final. Continúo haciendo esto, insertando cada carta en la posicion
que le corresponde, hasta que las tengo todas en orden.
Para simular esto en un programa necesitamos tener en cuenta algo: no podemos
desplazar los elementos así como así o se perderá un elemento. Lo que hacemos
es guardar una copia del elemento actual (que sería como la carta que tomamos)
y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el
elemento guardado en la posición del úultimo elemento que se desplazo.
*****************************************************************************/
strcpy(Reg.Metodo,"Insercion");
unsigned long CantLect=0; // Cantidad de Lecturas
unsigned long CantSwap=0; // Cantidad de Intercamvios

int i, j; //variables para el for
int Aux; //variable auxiliar

for (i=1; i Aux = Vec[i]; //le asigno a la auxiliar el valor del vactor en i
j = i - 1; //le asigno a j i-1
while ( (Vec[j] > Aux) && (j >= 0) ){ /*mientras el valor en "j"sea mayor
al auxiliar y "j" menor que cero,hacer*/
CantLect++;
Vec[j+1] = Vec[j]; //le asigno el valor en "j" a la posicion "j+1"
CantSwap++;
j--;
} //fin while
Vec[j+1] = Aux; //le asigno a la posicion "j+1" el valor de auxiliar
}//fin for
a_char (CantLect, CantSwap, Reg.CantLect, Reg.CantSwap);//cambia int por string
}//fin void metodo2

void Metodo3(sReg & Reg, tyVec Vec){ //"metodo de Shell Sort"
/*****************************************************************************
funcion: unicamente al inicio se obtiene el numero de salto(largo del vector/2).
Nota: la división es redondeada al entero próximo inferior.
Un ciclo externo girará mientras el Salto sea diferente de 0
Un ciclo interno irá pasando por cada posición del vector iniciando en 0
hasta que el contador del ciclo interno + el Salto sea igual al tama¤o del
vector. Dentro del ciclo interno se irán comparando la posición del vector
actual con la posición del vector actual + Salto.
Si vec[contador] > vec[contador + salto] entonces se intercambian los
números, y de esta manera van quedando los numero de menor valor a la
izquierda y los de mayor valor a la derecha del vector.
Al final se checa si hubo algún intercambio, si sí entonces se vuelve a
repetir el proceso con el mismo salto, de lo contrario el salto se decrementa
y se repite el proceso nuevamente.
*****************************************************************************/
strcpy(Reg.Metodo,"Shell Sort");
unsigned long CantLect=0; // Cantidad de Lecturas
unsigned long CantSwap=0; // Cantidad de Intercamvios

int Salto; //numero del salto = largo vector /2
int Cambios; //controla si hubo cambios en esa pasada
int Aux; //Auxiliar
int i; //for del ciclo interno

for(Salto=TOPE/2;Salto!=0;Salto/=2) {//ciclo externo: marca rango de comparacion
for(Cambios=1;Cambios!=0;){
Cambios=0; //inicializo en cero a cambios
for(i=Salto;i CantLect++;
if(Vec[i-Salto]>Vec[i]){
Aux=Vec[i]; //si es mayor lo guarda en la auxiliar
Vec[i]=Vec[i-Salto];//intercambia valores
Vec[i-Salto]=Aux; //intercambia valores
Cambios++;
CantSwap++;
}
}
}
}
a_char (CantLect, CantSwap, Reg.CantLect, Reg.CantSwap);//cambia int a string
}//fin void Metodo3

void Metodo4(sReg & Reg, tyVec Vec){//"metodo seleccion directa"
/****************************************************************************
Funcion: Se ubica en el primer registro del vector y guarda ese valor
como minimo mas la poscion de ese minimo (ciclo externo).
Desde la posicion siguiente al ciclo externo hasta el final del vector
busca si hay otro minimo. Va guardando en auxuliares el nuevo minimo y la
posicion del mismo (ciclo interno)
Cuando termina el ciclo interno si corresponde intercambia el minimo con el
que encontro. Repite sucesivamente el ciclo externo hasta y el interno hasta
que termina el vector
*****************************************************************************/
strcpy(Reg.Metodo,"Seleccion Directa");
unsigned long CantLect=0; // Cantidad de Lecturas
unsigned long CantSwap=0; // Cantidad de Intercamvios

int i; // Variable del ciclo Externo
int j; // varialbe del ciclo Interno
int k; // Auxiliar para guardar posicion del minimo
int menor; // Auxiliar para guardar el valor menor

for(i=0;i<=TOPE-1;i++) { //ciclo externo que recorre todo el vector
CantLect++;
menor=Vec[i];//Asigno a la variable el valor del Vector
k=i;//Asigno a la variable la posicion del menor
for(j=i+1;j externo hasta el fin del vector*/
CantLect++;
if(Vec[j] CantSwap++;
menor=Vec[j];
k=j;
}//fin del if
}//fin del for(j)
Vec[k]=Vec[i]; /*Cuando termino el ciclo interno asigno el valor menor en la posicion del ciclo externo*/
Vec[i]=menor;
CantSwap++;
}//fin del for (i)
a_char (CantLect, CantSwap, Reg.CantLect, Reg.CantSwap);
}//fin void metodo4


void Metodo5(sReg & Reg, tyVec Vec){ //INSORT
/****************************************************************************
Funcion: Recorre el Vector, desde el inicio hasta el fin,
y por cada posición Recorre los registros inferiores y verifica
su orden. Si el Valor actual, es menor al anterior, se moviliza,
sucesivamente hacia abajo.
*****************************************************************************/
strcpy(Reg.Metodo,"INSORT");
unsigned long CantLect=0; // Cantidad de Lecturas
unsigned long CantSwap=0; // Cantidad de Intercamvios

int x,aux,k;
for(x=0;x CantLect++;
aux=Vec[x];
k=x-1;
while(k>=0 && aux CantLect++;
CantSwap++;
Vec[k+1]=Vec[k];
k--;
}
CantSwap++;
Vec[k+1]=aux;
}
a_char (CantLect, CantSwap, Reg.CantLect, Reg.CantSwap);
}//fin void metodo5


void a_char (unsigned long Lecturas, unsigned long Swap, str10 & CantLect, str10 & CantSwap){
//Rutina que convierte las Cantidades leidas e intercambiadas a texto
ultoa(Lecturas, CantLect, 10);
ultoa(Swap, CantSwap, 10);
}// fin void a_char