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