METODOS DE ORDENAMIENTO

Iniciado por ANTÓN RAMIREZ, 12 Diciembre 2010, 05:34 AM

0 Miembros y 1 Visitante están viendo este tema.

ANTÓN RAMIREZ

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 :
Código (cpp) [Seleccionar]

/**
*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;
}
}


Garfield07

Bueno, Antón, bienvenido al foro!
Primero, por favor, tus próximos post en minuscula, se quitan las ganas de leer xD!

Luego, buen code, pero se podria refinar un poco, no se, me parece en exceso grande  no? Progr. estructurada, pero un poco mas...

luego te recomiendo que te pases a Linux, es mejor para empezar en codes C, pues si no te quedaras con Dev-Cpp para el resto de tu vida, y si quieres Windows, particiones.

Aparte, tu code solo es teoria, que esta bien, pero es mejor que hagas codigos codigos pequeños y utiles, que grandes y teoricos. Eso dejalo para los profes xD!!!


Bienvenido de nuevo y disfruta!


* Quiero cambiar el mundo, pero estoy seguro de que no me darían el código fuente.
* No estoy tratando de destruir a Microsoft. Ese será tan solo un efecto colateral no intencionado.
* Si compila esta bien, si arranca es perfecto.

¡Wiki elhacker.net!
Un saludo