sábado, 3 de agosto de 2013

Comparativa de rendimiento entre diferentes algoritmos de ordenación

Artículo perteneciente a la sección de algoritmos

Hola a todos,

En la sección de algoritmos hemos explicado ya diferentes algoritmos de ordenación y ya hemos explicado que los hay de mejores o de peores pero no hemos entrado en más detalles. Este artículo va a profundizar precisamente en el hecho de cuan rápidos son cada uno de los algoritmos.

Para hacer las pruebas de rendimiento he desarrollado un código muy sencillo que genera vectores desordenados de tamaño creciente de forma aleatoria y hace que los diferentes algoritmos los ordenen.

El código para hacer estas pruebas es el siguiente (por si lo queréis reaprovechar para algo):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void BubbleSort(int *v, int n)
{
int i,j = 0;
int temp = 0;
char bucle = 0;

do
{
bucle = 0;
for ( i = 0 ; i < (n-1-j) ; ++i )
{
if( v[i] > v[i+1] )
{
bucle = 1;
temp = v[i+1];
v[i+1] = v[i];
v[i] = temp;
}
}
j++;
}while(bucle);
}

void CocktailSort(int *v, int n)
{
int i , j = 0 ;
int temp = 0;
char bucle = 0;

do
{
bucle = 0;
for (i = j ; i < (n-1-j); ++i)
{
if(v[i] > v[i+1])
{
bucle = 1;
temp = v[i+1];
v[i+1] = v[i];
v[i] = temp;
}
}

if(bucle)
{
bucle = 0;
for (i = ( n - 1 - j ) ; i > j ; --i)
{
if(v[i] < v[i-1])
{
bucle = 1;
temp = v[i-1];
v[i-1] = v[i];
v[i] = temp;
}
}
}

j++;

}while(bucle);
}

void SelectionSort(int *v, int n)
{
int i,j,indmin=0;
int min = v[0];

for ( i = 0 ; i < (n-1) ; ++i)
{
indmin = i;
min = v[i];
for( j = i+1 ; j < n ; ++j)
{
if(v[j] < min )
{
indmin = j;
min = v[j];
}
}

v[indmin] = v[i];
v[i] = min;
}
}

int distribuir(int *v, int b, int t)
{
    int i;
    int pivote, valor_pivote;
    int temp;

    pivote = b;
    valor_pivote = v[pivote];

    for (i=b+1; i<=t; i++)
{
        if (v[i] < valor_pivote)
{
           pivote++;
           temp=v[i];
           v[i]=v[pivote];
           v[pivote]=temp;
}
    }
    temp=v[b];
    v[b]=v[pivote];
    v[pivote]=temp;
return pivote;
}

void RecursiveQuicksort(int *v, int b, int t)
{
int pivote;
    if(b < t)
{
pivote=distribuir(v , b, t);
        RecursiveQuicksort(v, b, pivote-1);
        RecursiveQuicksort(v, pivote+1, t);
    }
}

void QuickSort(int *v, int n)
{
RecursiveQuicksort(v, 0,n-1);
}

char IsSorted(int *v, int n)
{
int i;

for(i = 0 ; i < (n-1); ++i)
{
if( v[i] > v[i+1] )
return 0;
}
return 1;
}

void Randomize(int *v, int n)
{
int i;

for ( i = 0 ; i < n ; ++i )
{
v[i] = rand()%n;
}
}

#define TIMESTAMP printf("%d\t", ((clock() - time)*1000)/CLOCKS_PER_SEC );

int main(int argc, char *argv[])
{
int *v;
int *vbackup;
int n;
int time;

for( n = 4 ; n < 10000000; n *= 1.5 )
{
printf("%d\t",n);
v = malloc( sizeof(int) * n );
vbackup = malloc( sizeof(int) * n );

Randomize(vbackup,n);


memcpy(v,vbackup,n*sizeof(int));
time = clock();
BubbleSort(v,n);
TIMESTAMP
if (!IsSorted(v,n))
return 1;

memcpy(v,vbackup,n*sizeof(int));
time = clock();
CocktailSort(v,n);
TIMESTAMP
if (!IsSorted(v,n))
return 2;

memcpy(v,vbackup,n*sizeof(int));
time = clock();
SelectionSort(v,n);
TIMESTAMP
if (!IsSorted(v,n))
return 3;

memcpy(v,vbackup,n*sizeof(int));
time = clock();
QuickSort(v,n);
TIMESTAMP
if (!IsSorted(v,n))
return 4;

printf("\n");
free(v);
free(vbackup);
}

system("pause");
return 0;
}


Los resultados de la ejecución de este programa son los siguientes(tiempos en ms y N tamaño del vector a ordenar):

N BubbleSort CocktailSort SelectionSort QuickSort
4 0 0 0 0
6 0 0 0 0
9 0 0 0 0
13 0 0 0 0
19 0 0 0 0
28 1 0 0 0
42 0 0 0 0
63 0 0 0 0
94 0 0 0 0
141 0 0 0 0
211 0 1 0 0
316 0 1 0 0
474 1 1 1 0
711 3 2 1 1
1066 6 4 2 0
1599 12 9 4 0
2398 26 20 9 0
3597 57 46 20 1
5395 129 102 44 1
8092 292 228 99 2
12138 655 515 223 2
18207 1472 1157 509 4
27310 3337 2596 1128 4
40965 7503 5887 2535 7
61447 17403 13783 5828 12
92170 39226 31294 13847 19
138255 92045 72122 30289 29
207382 209775 164410 69914 49












Gráficamente estos datos se pueden representar tal que así:



Como podréis observar no es solo que el QuickSort sea más rápido, sino que su rendimiento respecto al resto mejora a medida que aumenta el tamaño del vector. Esto es por que su complejidad de cálculo aumenta según N*log(N), es decir, ordenar un vector 4 veces más grande implica 8 veces más tiempo, mientras que en el resto de algoritmos su ritmo de crecimiento es N^2, quiere decir, que un vector 4 veces más grande consume 16 veces más cálculos. Es por ello que para vectores de 200.000 elementos ( por ejemplo ) el algoritmo QuickSort es 5000 veces (literalmente) más rápido que el BubbleSort.

En breve haré algunas implementaciones con asm x86 y mutlithreading para que veáis que lo más importante no es la implementación de un algoritmo sino el coste computacional del algoritmo en si.

Espero que hayáis aprendido y os haya gustado

Nos vemos  

LordPakusBlog

0 comentarios :

Publicar un comentario

Related Posts Plugin for WordPress, Blogger...