Programación & Unix

Ordenación de Burbuja

Algoritmos | October 2nd

Este algoritmo compara los elementos del conjunto adyacente e intercambia sus valores si están en desorden. Este método da la apariencia de burbujas ya que los valores más pequeños suben como “burbujas”, mientras que los valores más grandes quedan en la parte de abajo; de ahí el nombre.

Análisis

Primero se toman los dos primeros elementos del conjunto (7 y 2) y los comparados. Al estar en desorden los intercambiamos.

Ahora tomamos el siguiente par de elementos (7 y 8) y nuevamente los comparamos. Este par esta en orden, por lo que no hay intercambio.

Tomamos el siguiente par (8 y 3) y nuevamente, este par esta en desorden por lo que hay intercambio.

Nuevamente tomamos el siguiente par (8 y 5) y los intercambiamos por estar en desorden.

Tomamos el siguiente par (8 y 4) y los intercambiamos.

De nuevo tomamos el siguiente par (8 y 6) y los intercambiamos.

Hasta ahora hemos recorrido el conjunto una sola vez y podemos ver que el elemento más grande ha llegado hasta el fondo, sin embargo, nuestro arreglo aún no esta ordenado.

Para terminar de ordenarlo debemos recorrer todo el conjunto las veces que sea necesario.

Código de la función

Una vez que hayamos entendido como funciona el método de burbuja para ordenar elementos podemos diseñar nuestro código fuente.

void burbuja(int array[], int size)
{
	for (int i = 1; i < size; i++)
	{
		for(int j = 0; j < size-1; j++)
		{
			if (array[j] > array[j+1])
			{
				std::swap(array[j], array[j+1]);
			}
		}
 	}
}

Código completo

Pongamos a prueba nuestra función en C++.

#include <iostream>

using namespace std;

void burbuja(int array[], int size)
{
	for (int i = 1; i < size; i++)
	{
		for(int j = 0; j < size-1; j++)
		{
			if (array[j] > array[j+1])
			{
				std::swap(array[j], array[j+1]);
			}
		}
	}
}

int main (int argc, char *argv[])
{
	int numeros[] = {8,5,2,7,6,3,4};

	/* Imprimimos el arreglo original */
	for (int i = 0; i < 7; ++i){
		cout << numeros[i] << " ";
	}

	cout << endl;

	burbuja(numeros, 7);

	/* Imprimimos el arreglo ordenado */
	for (int i = 0; i < 7; ++i){
		cout << numeros[i] << " ";
	}

	cout << endl;
}

$ g++ -o Burbuja Burbuja.cpp
$ ./Burbuja
8 5 2 7 6 3 4
2 3 4 5 6 7 8