viernes, 16 de septiembre de 2011

Comparacion de rapidez de algunos algoritmos de ordenamiento

Compara el tiempo que demoran algunos algoritmos en ordenar un vector de 10000 elementos


#include "stdafx.h"
#include "iostream"
#include "conio.h"
#include "stdlib.h" //Numeros random
#include "time.h" //Relojes

using namespace std;

const int n=10000;

void generarVector(int vector[])
{
int element = n;

for(int i=0;i<n;i++)
vector[i]=element--;//Asigna el valor de element avector[i] y al terminar esa linea el -- le resta 1 a element
}

void intercambio(int vector[],int i,int j)
{
int t=0;
t=vector[i];
vector[i]=vector[j];
vector[j]=t;
}

void bubbleSort(int vector[])
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(vector[i]>vector[j])
intercambio(vector,i,j);
}
}
}



void seleccionSort(int vector[])
{
int min;

for(int i=0;i<n-1;i++)
{
min=i;

for(int j=i+1;j<n;j++)
{
if(vector[min]>vector[j])
min=j;
intercambio(vector,i,j);
}
}
}

void quickSort(int vector[],int izq, int der )
{
int i,j,x;

i=izq;
j=der;

x=vector[(izq+der)/2];

do{
while((vector[i]<x)&&(j<=der))
{
i++;
}

while((x<vector[j])&&(j>izq))
{
j--;
}
if(i<=j)
{
intercambio(vector,i,j);
i++;
j--;
}
}
while(i<=j);

if(izq<j)
quickSort(vector,izq,j);
if(i<der)
quickSort(vector,i,der);
}

/* Al ordenar vectores pequeños con diferentes métodos de ordenamiento, la diferencia no se nota.
Pero no ocurre lo mismo cuando son gigantes vectores...
Veamos a continuación cuanto tardan con un vector de 10000 elementos
PD: El tiempo de ejecución empieza a correr desde que se ejecutó el programa
*/
void main()
{
clock_t t1,t2;

int V[n];

cout<<"Para cada algoritmo se genero un arreglo de 10000 elementos de mayor a menor"<<endl;
cout<<"estos son los tiempos que los diversos algoritmos de ordenamiento se tardaron en ordenarlo de menor a mayor:"<<endl;
cout<<"ESPERE POR FAVOR..."<<endl<<endl;

//Bubble Sort

generarVector(V);//Generamos vector

t1=clock(); //Capturamos el tiempo de la ejecución

bubbleSort(V);

t2=clock(); //Capturamos el tiempo de la ejecución

cout<<"Bubble Sort: "<<t2-t1<<" Ciclos"<<endl<<endl;//La diferencia entre las capturas hechas es lo que demoró el algoritmo


//Selection Sort

generarVector(V);

t1=clock();

seleccionSort(V);

t2=clock();

cout<<"Seleccion Sort: "<<t2-t1<<" Ciclos"<<endl<<endl;

//Quick Sort

generarVector(V);

t1=clock();

quickSort(V,0,n-1);

t2=clock();

cout<<"Quick Sort: "<<t2-t1<<" Ciclos"<<endl<<endl;

_getch();
}

No hay comentarios:

Publicar un comentario