HOLA TODOS LOS PROGRAMADORES ESPERO OBTENER BUENOS RESULTADOS Y HACER DISTINTAS AMISTADES E INFUNDIR EN ESTA RAMA , EN ESTA OPORTUNIDAD LES BRINDO UN TRABAJO HECHO EN BASE A LOS METODOS DE ORDENAMIENTO DE CAIRO , ESTAN TODOS ADAPTADOS Y LO ELEGANTE DE ESTE PROGRAMA ES QUE PUEDO SABER QUE METODO ES MAS RAPIDO PARA ELEMENTOS ALEATORIOS MAYORES DE 20000 Y ASI , ESPERO SUS OPINIONES Y COMENTARIOS ATTE, EL QUE DESEA MANDARME UN MENSAJE Y SE LO PUEDO FACILITAR O ALGUIEN ME PUEDE ORIENTAR COMO PUEDO COLGAR PROGRAMAS A ESTA PAGINA

ATTE : ANTON RAMIREZ , LEONARDO VLADIMIR  (ALUMNO UNI)

BUENO SI GUSTAN AQUI LES DEJO EL PSEUDOCIGO , SOLO ES CUESTION DE COMPILAR UTILIZO EL DEV-C++ , ESPERO COMENTARIOS :

/**
 *Nombre del programa: METODOS DE ORDENAMIENTO
 *Descripción: Este menu de ordenamiento contiene los 10 metodos de ordenamiento del libro de cairo ,aqui se podra mostrar 
 * cual es el mas rapido, cual es el mas lento . 
 * La forma que utilize para hallar el tiempo de cada ordenamiento para un mismo vector que tenga los mismos 
 * elementos aleatorios es ir al subprograma leerVector y poner en comentario a random cosa que siempre me 
 * va mostrar el mismo vector con los mismos elementos y por eso ya con el mismo vector generado siempre que 
 * compilo puedo distribuir el tiempo y saber quien es el mas rapido o mas lento. 
 *Autor: Anton ramirez,leonardo vladimir(20090231A)
 *Fecha: 05/10/2010
 *
 */
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 #include <time.h>
#define Max 120000
#define TOPE 1000
#define randomize (srand(time(0)))
#define random(num) (rand()%(num))
 
using namespace std;
 
int METODODEORDENAMIENTO();
void leerVector(int X[Max],int *dimX);
void mostrarVector(int X[Max],int dimX);
void ordenarxBurbuja(int X[Max],int dimX);
void ordenarxBurbuja_senal(int X [Max],int *dimX);
void ordenarxShaker_sort(int X[Max],int *dimX);
void ordenarxInsercion_directa(int X[Max],int *dimX);
void ordenarxInsercion_binaria(int X[Max],int *dimX);
void ordenarxSeleccion_directa(int X[Max],int dimX);
void ordenarxShell(int X[Max],int *dimX);
void ordenarxQuicksort_recursivo(int X[Max],int *dimX);
void Reduce_recursivo(int X[Max],int INI,int FIN);
void ordenarxQuicksort_iterativo(int X[Max],int *dimX);
int Reduce_iterativo(int X[Max],int INI,int FIN);
void ordenarxHeapsort(int X[Max],int *dimX);
void Inserta_monticulo(int X[Max],int *dimX);
void Elimina_monticulo(int X[Max],int *dimX);
 
int main()
{
 int Opcion,A[Max],na;
 do{
 Opcion = METODODEORDENAMIENTO();
 switch(Opcion)
 {
 case 1: {
 system("cls");
 printf("\n*******************Proceso de Lectura del Vector Aleatorio********************\n\n");
 leerVector(A,&na);
 system("pause");
 system("cls");
 break;
 } 
 case 2: {
 system("cls");
 printf("\n****************Mostramos el Vector Aleatorio Generado***********************\n\n");
 mostrarVector(A,na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 3: {
 system("cls");
 printf("\n******************Ordenamiento por el Metodo de Burbuja************************\n\n");
 ordenarxBurbuja(A,na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 4: {
 system("cls");
 printf("\n**************Ordenamiento por el Metodo de Burbuja con Senal****************\n\n");
 ordenarxBurbuja_senal(A,&na);
 printf("\n\n");
 system("pause");
 system("cls");
 break; 
 }
 case 5: {
 system("cls");
 printf("\n***************Ordenamiento por el Metodo de Shaker sort**********************\n\n");
 ordenarxShaker_sort(A,&na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 6: {
 system("cls");
 printf("\n***************Ordenamiento por el Metodo de Insercion Directa*****************\n\n");
 ordenarxInsercion_directa(A,&na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 7: {
 system("cls");
 printf("\n*******************Ordenamiento por el Metodo de Insercion Binaria************\n\n");
 ordenarxInsercion_binaria(A,&na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 8:{
 system("cls");
 printf("\n***************Ordenacion por el Metodo de Seleccion Directa******************\n\n");
 ordenarxSeleccion_directa(A,na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 9:{
 system("cls");
 printf("\n******************Ordenamiento por el Metodo de Shell**************************\n\n");
 ordenarxShell(A,&na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 10:{
 system("cls");
 printf("\n**************Ordenamiento por el Metodo Quicksort Recursivo*******************\n\n");
 ordenarxQuicksort_recursivo(A,&na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 11:{
 system("cls");
 printf("\n*************Ordenamiento por el Metodo Quicksort Iterativo*********************\n\n");
 ordenarxQuicksort_iterativo(A,&na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 }
 case 12:{
 system("cls");
 printf("\n************************Ordenamiento por el Metodo del Monticulo****************\n\n");
 ordenarxHeapsort(A,&na);
 printf("\n\n");
 system("pause");
 system("cls");
 break;
 } 
 } 
 }while(Opcion != 0); 
 return(0);
}
 
int METODODEORDENAMIENTO()
{
 int i;
 do
 {
 system("cls");
 printf("================================================================================\n"); 
 cout << "----------------M E T O D O S D E O R D E N A M I E N T O S-----------------";
 printf("================================================================================\n");
 cout << "\n ESCOJER EL MEJOR METODO PARA ORDENAR UN VECTOR: ";
 cout << "\n\n\r 0.- TERMINAR"; 
 cout << "\n\r 1.- LEER VECTOR ";
 cout << "\n\r 2.- MOSTRAR VECTOR ";
 cout << "\n\r 3.- ORDENAR X BURBUJA";
 cout << "\n\r 4.- ORDENAR X BURBUJA_SENAL";
 cout << "\n\r 5.- ORDENAR X SHAKER_SORT";
 cout << "\n\r 6.- ORDENAR X INSERCION_DIRECTA";
 cout << "\n\r 7.- ORDENAR X INSERCION_BINARIA";
 cout << "\n\r 8.- ORDENAR X SELECCION_DIRECTA";
 cout << "\n\r 9.- ORDENAR X SHELL";
 cout << "\n\r 10.- ORDENAR X QUICKSORT_RECURSIVO";
 cout << "\n\r 11.- ORDENAR X QUICKSORT_ITERATIVO";
 cout << "\n\r 12.- ORDENAR X HEAPSORT";
 cout << "\n\n\n\r Seleccione su opcion ---> ";
 cin >> i;
 }while(i<0 || i>12);
 return(i);
 
}
void leerVector(int X[Max],int *dimX)
{
 int n,i,val;
 randomize;//randomize es aqui donde si lo pongo como comentario me genera el mismo vector y es mas facil medir el tiempo..
 printf("INGRESE LA DIMENSION DE SU VECTOR A GENERAR: ");
 cin>>n;
 if(n<Max)
 {
 for(i=0;i<n;)
 { 
 val=random(TOPE);
 X[i]=val;
 i=i+1;
 }
 *dimX=n;
 printf("\n............Proceso de Lectura de Numeros Aleatorios Completada............\n\n");
 }
 else
 {
 printf("Dimension fuera de Rango...\n\n");
 }
}
 
void mostrarVector(int X[Max],int dimX)
{
 int i,val;
 if(dimX>0){
 for(i=0;i<dimX;)
 {
 val=X[i];
 printf("%3d ",val);
 i=i+1;
 }
 } 
 else{
 printf("Vector vacio ...!\n\n"); 
 }
}
void ordenarxBurbuja(int X[Max],int dimX)
{
 int i,j,aux;
 long ini,fin;
 ini = clock();// INICIA EL PROCESO DEL ORDENAMIENTO
 for(int i=0;i<dimX-1;i++){
 for(int j=i+1;j<dimX;j++){
 if(X[i]>X[j]){
 aux=X[j];
 X[j]=X[i];
 X[i]=aux;
 }
 }
 }
 mostrarVector(X,dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
void ordenarxBurbuja_senal(int X [Max],int *dimX)
{
 bool BAND=false;
 int i=0,j,aux,
 N=*dimX-1;
 long ini,fin;
 ini = clock();
 while((i<=N-1)&&(!BAND))
 {
 BAND=true;
 for(j=0;j<=N-1;j++)
 {
 if(X[j]>X[j+1])
 {
 aux=X[j];
 X[j]=X[j+1];
 X[j+1]=aux;
 BAND=false;
 }
 }
 i=i+1;
 }
 mostrarVector(X,*dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
void ordenarxShaker_sort(int X[Max],int *dimX)//METODO DE LA SACUDIDA
{
 int i,IZQ=1,aux,N=*dimX-1,k=N,DER=N;
 long ini,fin;
 ini = clock();
 while(DER>=IZQ)
 {
 for(i=DER;i>=IZQ;i--)
 {
 if(X[i-1]>X[i])
 {
 aux=X[i-1];
 X[i-1]=X[i];
 X[i]=aux;
 k=i;
 }
 }
 IZQ=k+1;
 for(i=IZQ;i<=DER;i++)
 {
 if(X[i-1]>X[i])
 {
 aux=X[i-1];
 X[i-1]=X[i];
 X[i]=aux;
 k=i;
 }
 }
 DER=k-1;
 }
 mostrarVector(X,*dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
void ordenarxInsercion_directa(int X[Max],int *dimX)
{
 int i,aux,k,N=*dimX-1;
 long ini,fin;
 ini = clock();
 for(i=1;i<=N;i++)
 {
 aux=X[i];
 k=i-1;
 while((k>=0)&&(aux<X[k]))
 {
 X[k+1]=X[k];
 k=k-1;
 }
 X[k+1]=aux;
 }
 mostrarVector(X,*dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
void ordenarxInsercion_binaria(int X[Max],int *dimX)
{
 int i,aux,IZQ,DER,M,j,N=*dimX-1;
 long ini,fin;
 ini = clock();
 for(i=1;i<=N;i++)
 {
 aux=X[i];
 IZQ=0;
 DER=i-1;
 while(IZQ<=DER)
 {
 M=(int)((IZQ+DER)/2);
 if(aux<=X[M]){
 DER=M-1;
 }
 else
 {
 IZQ=M+1;
 } 
 }
 j=i-1;
 while(j>=IZQ)
 {
 X[j+1]=X[j];
 j=j-1;
 }
 X[IZQ]=aux;
 }
 mostrarVector(X,*dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
//ORDENAMIENTO POR SELECCION
/*ESTE METODO CONSISTE EN ENCONTRAR EL MENOR ELEMENTO DEL ARREGLO
Y UBICARLO AL PRINCIPIO... LUEGO SE BUSCA EL MENOR ELEMENTO DEL RESTO Y SE
UBICA EN SEGUNDO LUGAR. SE REPITE EL PROCESO N-1 VECES*/
void ordenarxSeleccion_directa(int X[Max],int dimX)
{
 int i,MENOR,k,j;
 time_t ini,fin;
 ini = clock();// inicia el calculo del metodo de ordenamiento
 
 for(i=0;i<dimX;)
 {
 MENOR=X[i];
 k=i;
 for(j=i+1;j<dimX;)
 {
 if(X[j]<MENOR)
 {
 MENOR=X[j];
 k=j;
 }
 j=j+1;
 }
 X[k]=X[i];
 X[i]=MENOR;
 i=i+1;
 }
 mostrarVector(X,dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(double)CLOCKS_PER_SEC);
}
 
void ordenarxShell(int X[Max],int *dimX)
{
 int i,aux,N=*dimX-1,INT=N+1;
 bool BAND;
 long ini,fin;
 ini = clock();
 while(INT>0)
 {
 INT=(int)(INT/2);
 BAND=true;
 while(BAND)
 {
 BAND=false;
 i=0;
 while((i+INT)<=N)
 {
 if(X[i]>X[i+INT])
 {
 aux=X[i];
 X[i]=X[i+INT];
 X[i+INT]=aux;
 BAND=true;
 }
 i=i+1;
 }
 }
 }
 mostrarVector(X,*dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
void ordenarxQuicksort_recursivo(int X[Max],int *dimX)
{
 int N=*dimX-1;
 long ini,fin;
 ini = clock();
 Reduce_recursivo(X,0,N);
 mostrarVector(X,*dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
void Reduce_recursivo(int X[Max],int INI,int FIN)
{
 int IZQ=INI,DER=FIN,POS=INI,aux;
 bool BAND=true;
 while(BAND)
 {
 BAND=false;
 while((X[POS]<=X[DER])&&(POS!=DER))
 {
 DER=DER-1;
 }
 if(POS!=DER)
 {
 aux=X[POS];
 X[POS]=X[DER];
 X[DER]=aux;
 POS=DER;
 while((X[POS]>=X[IZQ])&&(POS!=IZQ))
 {
 IZQ=IZQ+1;
 }
 if(POS!=IZQ)
 {
 BAND=true;
 aux=X[POS];
 X[POS]=X[IZQ];
 X[IZQ]=aux;
 POS=IZQ;
 }
 }
 }
 if((POS-1)>INI)
 {
 Reduce_recursivo(X,INI,POS-1);
 }
 if(FIN>(POS+1))
 {
 Reduce_recursivo(X,POS+1,FIN);
 }
}
void ordenarxQuicksort_iterativo(int X[Max],int *dimX)
{
 int full=0,I,F,POS,N=*dimX-1,P1[Max],P2[Max];
 long ini,fin;
 P1[full]=0;//PILA MENOR
 P2[full]=N;//PILA MAYOR
 ini = clock();
 while(full>=0)
 {
 I=P1[full];
 F=P2[full];
 full=full-1;
 POS=Reduce_iterativo(X,I,F);
 if(I<(POS-1))
 {
 full=full+1;
 P1[full]=I;
 P2[full]=POS-1;
 }
 if(F>(POS+1))
 {
 full=full+1;
 P1[full]=POS+1;
 P2[full]=F;
 }
 }
 mostrarVector(X,*dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
int Reduce_iterativo(int X[Max],int INI,int FIN)
{
 int IZQ=INI,DER=FIN,aux,POS=INI;
 bool BAND=true;
 while(BAND)
 {
 while((X[POS]<=X[DER])&&(POS!=DER))
 {
 DER=DER-1;
 }
 if(POS==DER)
 {
 BAND=false;
 }
 else
 {
 aux=X[POS];
 X[POS]=X[DER];
 X[DER]=aux;
 POS=DER;
 while((X[POS]>=X[IZQ])&&(POS!=IZQ))
 {
 IZQ=IZQ+1;
 }
 if(POS==IZQ)
 {
 BAND=false;
 }
 else
 {
 aux=X[POS];
 X[POS]=X[IZQ];
 X[IZQ]=aux;
 POS=IZQ;
 }
 }
 }
 //return(POS);// POS variable es una variable donde se almacena el resultado del algoritmo.
}
 
void ordenarxHeapsort(int X[Max],int *dimX)//METODO DEL MONTICULO
{//METODO EFICIENTE QUE TRABAJA CON ARBOLES .
 long ini,fin;
 ini = clock();
 Inserta_monticulo(X,dimX);
 Elimina_monticulo(X,dimX);
 mostrarVector(X,*dimX);
 fin=clock();
 printf("\n\ntiempo en segundos %f s\n\n",(fin-ini)/(float)CLOCKS_PER_SEC);
}
 
void Inserta_monticulo(int X[Max],int *dimX)
{
 int i,k,aux,N=*dimX-1;
 bool BAND;
 for(i=1;i<=N;i++)
 {
 k=i;
 BAND=true;
 while((k>0)&&BAND)
 {
 BAND=false;
 if(X[k]>X[(int)(k/2)])
 {
 aux=X[(int)(k/2)];
 X[(int)(k/2)]=X[k];
 X[k]=aux;
 k=(int)(k/2);
 BAND=true;
 }
 }
 }
}
 
void Elimina_monticulo(int X[Max],int *dimX)
{
 int i,aux,IZQ,DER,k,AP,MAYOR,N=*dimX-1;
 bool BOOL;
 for(i=N;i>=1;i--)
 {
 aux=X[i];
 X[i]=X[0];
 IZQ=1;
 DER=2;
 k=0;
 BOOL=true;
 while((IZQ<i)&&BOOL)
 {
 MAYOR=X[IZQ];
 AP=IZQ;
 if((MAYOR<X[DER])&&(DER!=i))
 {
 MAYOR=X[DER];
 AP=DER;
 }
 if(aux<MAYOR)
 {
 X[k]=X[AP];
 k=AP;
 }
 else
 {
 BOOL=false;
 }
 IZQ=k*2;
 DER=IZQ+1;
 }
 X[k]=aux;
 }
}