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  

Algoritmo de ordenación de Burbuja bidireccional (ordenación por sacudida o Cocktail Sort)

Artículo perteneciente a la sección de algoritmos

Este artículo es una evolución del algoritmo de ordenación por burbuja

Hola a todos,

Si ya habéis visto como funciona el algoritmo de ordenación por burbuja habréis observado que es fácil llevar los números grandes hasta el final de la lista, pero que es complicado llevar los números pequeños al inicio de la lista. Dependiendo de como estén ordenados los números a priori se puede llegar a tardar bastante en ordenarlos.

La solución es sencilla... ordenar con el método de burbuja y cuando llegamos al final de la primera iteración, no volver a realizar el cálculo desde el principio sino que empezaremos desde el final hasta al inicio. De esta manera siempre se consigue que tanto los números pequeños como los números grandes se desplacen a los extremos de la lista lo más rápido posible. Esto otorga el beneficio adicional que la lista cada vez se nos hace más pequeña (en los extremos de la lista vamos almacenando los elementos defnifitivos que nunca más se tendrán que mirar).

El código es tal que así (solo tiene fines educativos, no es una implementación terriblemente eficiente):

void LPVector::CocktailSort(void)
{
int i , j = 0 ;
float temp = 0.0;

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

if(!this->IsSorted())
{
for (i = ( n - 1 - j ) ; i > j ; --i)
{
if(v[i] < v[i-1])
{
temp = v[i-1];
v[i-1] = v[i];
v[i] = temp;
}
}
}

j++;

}while(!this->IsSorted());
}

Espero que esta idea tan sencilla para mejorar el algoritmo de burbuja os inspire para buscarle más soluciones a vuestros problemas.

Nos vemos

Algoritmo de ordenamiento por burbuja (BubbleSort)

Artículo perteneciente a la sección de algoritmos

Hola a todos,

El método de ordenamiento por burbuja (más conocido como BubbleSort) es uno de los algoritmos más sencillos para ordenar listas de números.

Su funcionamiento es extremadamente simple.
1. Se comparan los dos primeros números de la lista y se ordenan (el menor se pone en la posición más baja y el mayor se pone en la posición más alta de los dos)

2. Se compara el segundo con el tercer elemento y se repite la misma operación. Se aplica este sistema hasta el final de la lista de números.

3. Cuando se llega al final, se vuelve a empezar desde el principio. Cuando en una de estas iteraciones no se tiene que hacer ningún cambio de elementos significa que ya se ha hecho todo el proceso de ordenación.

Para realizar el código de este tutorial he tomado de base el del MathEngine que escribí hace ya unos años. En cuanto tenga un rato arreglaré todo el código antiguo, le daré una buena repasada a la calidad del código de este proyecto y lo subiré al svn.

Aquí tenéis un ejemplo de código de como realizar el BubbleSort (n es el número de elementos del vector y v es el vector como tal):

void LPVector::BubbleSort(void)
{
int i, j = 0 ;
float temp = 0.0;

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

char LPVector::IsSorted(void)
{
int i;

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

Tal y como he dicho antes es de los algoritmos de ordenación más sencillos de implementar que puedan existir, el problema es que su rendimiento no es demasiado bueno. En capítulos posteriores haremos una comparativa de rendimientos entre diferentes métodos de ordenación.

Si queréis hacer la prueba de que funciona correctamente podéis ejecutar algo de este estilo:

int main (int argc, char* argv[])
{
    LPVector v1;
float vecsorted[5] = { 1.0,2.0,3.0,4.0,5.0 };
float vecinverted[5] = { 5.0,4.0,3.0,2.0,1.0};
float vecrandom[5] = { 2.0, 4.0, 1.0, 5.0, 3.0};

   cout << endl << "Vector ya ordenado " << endl;

v1.Set(5,vecsorted);
v1.print();

cout << endl;

v1.BubbleSort();
v1.print();


cout << endl << "Vector ordenado al reves" << endl;

v1.Set(5,vecinverted);
v1.print();

cout << endl;

v1.BubbleSort();
v1.print();


cout << endl << "Vector totalmente desordenado " << endl;

v1.Set(5,vecrandom);
v1.print();

cout << endl;

v1.BubbleSort();
v1.print();

cout << endl;

    //Eliminamos los vectores
    v1.Delete();

    system("PAUSE");
}

Y la ejecución debería daros algo del estilo de :

Como nota final, si os fijais, el nombre de ordenamiento por burbuja es totalmente correcto debido a que los elementos del vector se van desplazando arriba y abajo como si fueran burbujas.

Espero que os haya gustado

Nos vemos