El algoritmo de la burbuja

El algoritmo de la burbuja es uno de los métodos de ordenación más conocidos. Sin embargo, no se trata de un algoritmo eficiente desde el punto de vista computacional, ni tampoco se trata de un algoritmo que sea fácil de entender, y por tanto, que pueda utilizarse con fines pedagógicos. Se trata, simplemente, de un algoritmo malo con un nombre divertido. El mundo es así. Veamos el algoritmo:

función burbuja(v, n)
    repetir desde i:=n hasta 1
        repetir desde j:=1 hasta i-1    
            si v[j+1] < v[j] entonces
                aux    := v[j]
                v[j]   := v[j+1]
                v[j+1] := aux
            fin si
        fin repetir
    fin repetir
fin función

El algoritmo se basa en dos bucles que están anidados uno dentro de otro. Al final de cada iteración del primer bucle nos aseguramos que el i-ésimo elemento es el mayor de los i-1 primeros elementos del vector, y el segundo bucle es el encargado de que esto sea así, mediante el intercambio de los números que sean necesarios. Imaginemos, por ejemplo, que tenemos que ordenar la siguiente secuencia de números:

    [12, 23, 14, 19, 3]

Cuando i vale 5, el bucle interior va desde 1 hasta 4, comparando cada elemento con su siguiente, y en el caso de que el siguiente sea menor, intercambiándolos. Primero comparamos el 12 con el 23, y como están ordenados no sucede intercambio; después comparamos el 23 con el 14, que al ser menor, hay que intercambiarlos; a continuación comparamos el 23 (que había sido intercambiado) con el 19, y también hay que intercambiarlos. Y finalmente comparamos nuevamente el 23 con el 3, y lo volvemos a intercambiar. Tal y como muestra la siguiente figura:

Como podemos comprobar, el 23 ya está situado en su posición (para i=5 nos aseguramos que la posición 5 contiene el valor correcto). En la siguiente iteración situaríamos el 19 en su posición correcta, y así sucesivamente hasta ordenar completamente el vector. Se llama algoritmo de la burbuja por la forma en que tienen los números mayores de subir hacia arriba en el vector, como si fueran burbujas flotando en un líquido.