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