Implementación y Comparación de Algoritmos de Ordenamiento en C++

Ingeniería informática, , , ,

Implementación y Comparación de Algoritmos de Ordenamiento en C++

#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 Señal****************\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 Inserción 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 Inserción Binaria************\n\n»);

ordenarxInsercion_binaria(A,&na);

printf(«\n\n»);

system(«pause»);

system(«cls»);

break;

}

case 8:{

system(«cls»);

printf(«\n***************Ordenación por el Metodo de Selección 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 Montículo****************\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_SEÑAL»;

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 opción —> «;

cin >> i;

}while(i<0 || i>12);

return(i);

}

void leerVector(int X[Max],int *dimX)

{

int n,i,val;

randomize;//randomize es aquí donde si lo pongo como comentario me genera el mismo vector y es más fácil 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 Números Aleatorios Completada…………\n\n»);

}

else

{

printf(«Dimensión 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 vacío …!\n\n»);

}

}

Método de Ordenamiento de Burbuja

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);

}

Método de Ordenamiento de Burbuja con Señal

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);

}

Método de Ordenamiento Shaker Sort

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);

}

Método de Ordenamiento de Inserción Directa

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);

}

Método de Ordenamiento de Inserción Binaria

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);

}

Método de Ordenamiento de Selección Directa

//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 método 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);

}

Método de Ordenamiento Shell

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);

}

Método de Ordenamiento Quicksort Recursivo

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

 {

 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]

 {

 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

 {

 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

 {

 MAYOR=X[IZQ];

 AP=IZQ;

 if((MAYOR

 {

 MAYOR=X[DER];

 AP=DER;

 }

 if(aux

 {

 X[k]=X[AP];

 k=AP;

 }

 else

 {

 BOOL=false;

 }

 IZQ=k*2;

 DER=IZQ+1;

 }

 X[k]=aux;

 }

}

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.