Ejemplo 5 - Ordenamiento de vectores con el algoritmo de burbuja

Objetivo

Comprender el funcionamiento del algoritmo de ordenamiento de burbuja.

Enunciado

El algoritmo de burbuja se basa en llevar a cabo recorridos por el vector comparando el elemento de cada celda con el de la siguiente celda.
En cada momento se intercambian los elementos o se dejan tal y como están para asegurar que el valor más alto encontrado “suba” o se desplace hacia la derecha.
El efecto de esto es lograr que el valor más alto o bajo (dependiendo de la forma en que se programe) “suba” hasta la última posición del vector a modo de “burbuja”.
Si este proceso se repite tantas veces como elementos tiene el vector todos los elementos subieron hasta la posición más alta que podían encontrar asegurando que el vector ha quedado ordenado.

Solución

El algoritmo de burbuja se basa en llevar a cabo recorridos por el vector haciendo que el valor más alto encontrado desde el inicio del vector “suba” hasta las últimas posiciones del vector a modo de “burbuja”. Si este proceso se repite tantas veces como elementos tiene el vector se puede asegurar que el vector ha quedado ordenado.
En la práctica primero se compara el elemento de la primera posición del vector con el siguiente, si este es mayor se intercambian entre sí, si no se compara el segundo elemento con el tercero, si el segundo es mayor que el tercero se intercambian, si no, se repite el proceso a partir de la siguiente posición hasta llegar al final del vector.
Los intercambios llevados a cabo de esta forma aseguran que el más alto quedó al final luego de ese ciclo. Este proceso se repite nuevamente tantas veces como elementos tiene el vector.

El siguiente método muestra los dos métodos más importantes del algoritmo de burbuja.

     /**
* REQUIERE: Que el vector sea diferente de null y las posiciones "i" y "j" sean válidas
* EFECTUA: Intercambia el valor de la posición "i" con el de la posición "j"
* MODIFICA: El vector, especificamente las celdas vector[i] y vector[j]
*/
private void intercambiar(int i, int j){
double temp = vector[i];
vector[i]=vector[j];
vector[j]=temp;
} /**
* REQUIERE: Que el vector sea diferente de null
* EFECTUA: Ordena los elementos del vector con el algoritmo de burbuja
* MODIFICA: El vector al ordenar los elementos ascendentemente
*/ public void ordenar(){
int cantidadDeRecorridos = vector.length-1; // Hay que hacer tantos recorridos como elementos hay
// Como hay length cantidad de elementos hay que hacer esa cantidad de recorridos menos 1 // ya que en cada iteración se compara una celda con "la siguiente" int posicionLimite = vector.length-1; // El indice llega hasta este límite length-1
for(int recorrido=0; recorrido< cantidadDeRecorridos; recorrido++) {
// Recorre desde el inicio hasta llegar a donde están los elementos ya ordenados
for(int pos=0; pos < posicionLimite; pos++) {
// si encuentra uno mayor al siguiente lo intercambia
if(vector[pos] > vector[pos+1]){
intercambiar(pos,pos+1);
}
}
posicionLimite--; // El mayor quedó al final asi que la próxima llega hasta una posició antes
}
}

Si se agregan seis elementos tal y como se muestra a continuación:

 

Se produce el siguiente resultado. Note el orden de los elementos del vector antes y después del ordenamiento.

Código Fuente

Vector.java

PruebaBurbuja.java