El algoritmo de ordenación por el método de la burbuja, también conocido como intercambio directo, es uno de los más simples que se conocen.

Se basa en una serie de intercambios entre elementos adyacentes. Esos intercambios dan la impresíón de que cada elemento va ascendiendo a través del array acercándose cada vez más a su posición final, recordando a cómo ascienden las burbujas de gas en un líquido.

A efectos prácticos, el algoritmo de la burbuja no es adecuado prácticamente para ninguna situación, ya que realiza muchas comparaciones y muchos intercambios. Los hay similares que se comportan bastante mejor. Su interés es más bien teórico, ya que sirve para establecer comparativas con otros métodos y extraer conclusiones teóricas.

No obstante, es un algoritmo sencillo y vistoso que se sigue viendo en casi cualquier curso o asignatura de programación. Muchos profesores prefieren no perder tiempo con este algoritmo en las clases de programación... bueno... quizá sea una decisión acertada. Sin embargo, es uno de los imprescindibles en algoritmia... así que vamos a echarle un vistazo.

Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).

Es un algoritmo estable de ordenación interna, y su complejidad temporal en el peor caso es de O(n²), mientras que en el mejor caso -que el array ya esté totalmente ordenado- puede llegar a Ω(n) siendo n el tamaño del array a ordenar. En cuanto a la complejidad espacial, es muy ahorrativo: tan solo necesita una variable temporal para realizar los intercambios, así que su gasto de memoria es constante, sea cual sea el tamaño del array.

El algoritmo consiste en realizar varias pasadas sobre el array, logrando que en cada pasada el elemento de mayor valor se coloque al final del array. Para lograrlo, en cada pasada es necesario recorrer el array realizando comparaciones e intercambios. Por eso, se suele implementar con dos bucles, uno anidado dentro del otro. El bucle exterior realiza las pasadas y el interior recorre el array realizando comparaciones e intercambios.

Vamos a intentar ver informalemente el funcionamiento del algoritmo. Supondremos que el array tiene n elementos.

• Realizaremos n-1 pasadas. En cada una de ellas lograremos que el elemento de mayor valor se sitúe al final. El motivo de realizar n-1 pasadas y no n es que si en cada pasada logramos ordenar un elemento, cuando tengamos en orden los n-1 del final del array el elemento que queda es necesariamente el más pequeño de todos.
• En cada pasada recorreremos el array empezando por el principio hasta un cierto punto, comparando cada elemento con el siguiente, y si un elemento y el siguiente no están en orden, los intercambiamos de posición, logrando que el mayor de ellos vaya ascendiendo por el array.
• En la primera pasada, compararemos cada uno de los n-1 primeros elementos con el siguiente, y lograremos que en la última posición se coloque el mayor de ellos.
• En la segunda pasada, compararemos cada uno de los n-2 primeros elementos con el siguiente. No llegaremos a hacer ninguna comparación que implique al último elemento del array, porque sabemos que ese ya lo colocó en orden la primera pasada. Al término de la segunda pasada quedará también en orden el penúltimo elemento del array.
• En la tercera pasada haremos lo mismo con los n-3 primeros elementos, logrando colocar el antepenúltimo elemento... y así sucesivamente, hasta que tengamos colocados los n-1 últimos elementos. Cuando estemos en esa situación, el primer elemento también estará en orden, ya que será el más pequeño de todos.

Vemos un ejemplo sencillo. Supongamos que queremos ordenar estos valores con el algoritmo de la burbuja: 45, 52, 21, 37, 49, así pues, n=5

1ª pasada: comparamos cada uno de los cuatro primeros (n-1) con los que le siguen. Si un elemento no está en orden con respecto al siguiente, los intercambiamos de sitio y seguimos. El elemento de mayor valor (52) irá "ascendiendo" hasta la última posición.

45, 52, 21, 37, 49 → Comparar 45 y 52. (1º y 2º) Están en orden. Seguimos.
45, 52, 21, 37, 49 → Comparar 52 y 21. (2º y 3º) No están en orden. Intercambio.
45, 21, 52, 37, 49 → seguimos
45, 21, 52, 37, 49 → Comparar 52 y 37 (3º y 4º). No están en orden. Intercambio.
45, 21, 37, 52, 49 → seguimos
45, 21, 37, 52, 49 → Comparar 52 y 49. (4º y 5º). No están en orden. Intercambio.
45, 21, 37, 49, 52 → Ya hemos terminado esta pasada.
45, 21, 37, 49, 52 → El 5º elemento ya está en su sitio.

2ª pasada: comparamos cada uno de los tres primeros (n-2) con los que le siguen. No llegamos a hacer comparaciones que involucren al 5º elemento, porque la primera pasada hizo que el mayor de todos los elementos ocupara la última posición, con lo cual, sabemos que ese ya está en su sitio. Trabajaremos sólo con los cuatro que quedan.

45, 21, 37, 49, 52 → Comparar 1º y 2º. No están en orden. Intercambio.
21, 45, 37, 49, 52 → seguimos
21, 45, 37, 49, 52 → Comparar 2º y 3º. No están en orden. Intercambio.
21, 37, 45, 49, 52 → seguimos
21, 37, 45, 49, 52 → Comparar 3º y 4º. Están en orden. Pasada terminada.
21, 37, 45, 49, 52 → El 4º elemento ya está en su sitio. (Fíjate en que el array ya está en orden, pero algoritmicamente, eso no lo sabemos).

3ª pasada: Comparamos cada uno de los dos primeros (n-3) con los siguientes.

21, 37, 45, 49, 52 → 1º y 2º. Están en orden. Seguimos.
21, 37, 45, 49, 52 → 2º y 3º. Están en orden. Pasada terminada.
21, 37, 45, 49, 52 → Ya tenemos tres en orden.

4ª y última pasada: Comparamos el primero con el segundo.

21, 37, 45, 49, 52 → 1º y 2º están en orden. Pasada terminada.
21, 37, 45, 49, 52 → Ya tenemos los cuatro últimos en orden.

21, 37, 45, 49, 52 → Así pues, el primero también lo está.

Expresado en pseudocódigo, podría ser algo como esto:

algoritmo burbuja( A : array de n elementos indizados de 1 a n)
  para i desde 1 hasta n-1 hacer: //las n-1 pasadas
       para j desde 1 hasta n-i hacer: //el recorrido
         si A[j] > A[j+1] entonces //Si no están en orden
           intercambiar A[j] y  A[j+1] //Se intercambian
       fin para
  fin para
fin algoritmo

Por supuesto, es necesario adaptarlo a las necesidades concretas. Por ejemplo, en C/C++/C#/Java, etc... los índices de los arrays empiezan en 0 y terminan en n-1. El array a ordenar no tiene por qué ser de enteros, puede ser de cualquier cosa ordenable, pero entonces, análogamente, la operación de comparación (">") debe ser sustituida por la operación que nos compare nuestros elementos por el criterio que nosotros queramos.

¿Todavía no ha quedado claro? Bueno... yo no tengo paciencia para realizar animaciones, así que mira esta animación de baja tecnología e intenta asimilar cada paso con el algoritmo en pseudocódigo de arriba.

(La música es Easy Winners de Scott Joplin, obtenida de la página de Warren Trachtman . Gracias, Warren)

OJO CON LOS ÍNDICES

Lo importante de un algoritmo no es que lo memorices ni que lo intentes traducir literalmente a un lenguaje de programación concreto.

Lo importante es que lo entiendas y seas capaz de implementarlo adaptándolo a cualquier lenguaje sin traducirlo literalmente.

En el algoritmo de la página anterior hay un importante reto que a veces es dificil de superar: los índices. En el pseudocódigo se asume que el array de n elementos se indiza desde 1 hasta n. Es decir, el primer elemento es el número 1 y el último es el número n.

En algunos lenguajes de programación (como Pascal o Delphi, por ejemplo) es posible utilizar arrays que empiecen por un índice 1, como en el pseudocódigo. Sin embargo, en muchos otros (como C/C++/C# o Java) los arrays siempre empiezan por el índice 0. Es decir los elementos de un array de n elementos se indizan con índices que empiezan en 0 y terminan en n-1.

Esto no supone mayor problema que dedicar un rato a pensar cómo ajustar los índices para que el algoritmo siga haciendo lo que debe. Tenemos dos posibles opciones evidentes: Alterar los índices en las declaraciones de los bucles (restando 1) o bien alterar los índices en el contenido de los bucles, cuando se accede a los elementos (restando 1 también). Personalmente, siempre me ha parecido más fácil la segunda opción.

Mira cómo se podría hacer en C#. Es facilmente extrapolable a otros lenguajes.

Ejemplo: alterando los índices en las declaraciones de los bucles:

static void BurbujaEnteros(int[] A)
        {
        int n = A.Length;
        int iaux;
        for (int i=0; i < n-1;i++) 
            {
                for (int j = 0; j < n - i - 1;j++ )
                {
                    if (A[j] > A[j + 1])
                    {
                        iaux = A[j];
                        A[j] = A[j + 1];
                        A[j + 1] = iaux;
                    }
                }
            }
        }

Ejemplo: alterando los índices cuando se accede al array

static void BurbujaEnteros(int[] A)
        {
            int n = A.Length;
            int iaux;
            for (int i = 1; i <= n-1 ; i++)
            {
                for (int j = 1; j <= n - i; j++)
                {
                    if (A[j-1] > A[j])
                    {
                        iaux = A[j-1];
                        A[j-1] = A[j];
                        A[j] = iaux;
                    }
                }
            }
        }

Aunque pueda no parecerlo, es el mismo algoritmo.

UN EJEMPLO CON OBJETOS EN C#.

Pero ¿por qué conformarnos con ordenar enteros? En realidad, el algoritmo de la burbuja puede ordenar cualquier cosa siempre que tengamos un criterio de ordenación.

Veamos... Vamos a crear una clase Persona con un par de variables de variables de instancia: nombre y edad.

Vamos a dotar a la clase con un par de criterios de comparación: uno para decidir si una persona va antes que otra según su nombre alfabétiacamente, y otro para hacer lo mismo con la edad, sólo como ejemplo para ver cómo ordenar un array de personas por un par de criterios distintos.

class Persona
    {
        public String nombre;
        public int edad;
 
        public Persona(String nombre, int edad)
        {
            this.nombre = nombre;
            this.edad = edad;
        }
 
        public bool esMayorPorNombreQue(Persona p)
        {
            return this.nombre.ToUpper().
                   CompareTo(p.nombre.ToUpper())>0;
        }
 
        public bool esMayorPorEdadQue(Persona p)
        {
            return this.edad > p.edad;
        }
        public override String ToString() 
        {
            return nombre + ":" + edad;
        }
 
    }

Ya podemos organizar una prueba. Vamos a crear un array con cinco personas, y aplicaremos el algoritmo de la burbuja utilizando el criterio de la edad y luego el del nombre. Imprimiremos por la consola el array para comprobar que en efecto, el algoritmo está actuando.

static void OrdenarPorEdad(Persona[] A)
        {
            int n=A.Length;
            Persona paux;
            //bucle exterior. n-1 pasadas.
            for (int i = 1; i <= n-1; i++)
            {
                for (int j = 1; j <= n-i ; j++)
                {
                    if (A[j-1].esMayorPorEdadQue(A[j]))
                    {
                        //intercambio
                        paux = A[j-1];
                        A[j-1] = A[j];
                        A[j] = paux;
                    } //if
                } //for j
            } //for i
        } //OrdenarPorEdad
 
 
 
        static void OrdenarPorNombre(Persona[] A)
        {
            int n = A.Length;
            Persona paux;
            //bucle exterior. n-1 pasadas.
            for (int i = 0; i < n - 1; i++)
            {
                for (int j = 0; j < n - i -1; j++)
                {
                    if (A[j].esMayorPorNombreQue(A[j + 1]))
                    {
                        //intercambio
                        paux = A[j];
                        A[j] = A[j + 1];
                        A[j + 1] = paux;
                    } //if
                } //for j
            } //for i
        } //OrdenarPorEdad
 
 
 
        static void Main(string[] args)
        {
 
            Persona[] A = new Persona[5];
            A[0] = new Persona("Luis", 44);
            A[1] = new Persona("Antonia", 29);
            A[2] = new Persona("Pepe", 20);
            A[3] = new Persona("Maria", 13);
            A[4] = new Persona("Alberto", 56);
 
            Console.WriteLine("Sin orden");
            for (int i = 0; i < A.Length; i++)
            {
                Console.WriteLine(A[i]);
            }
 
            OrdenarPorEdad(A);
            Console.WriteLine();
            Console.WriteLine("Orden por edad");
            for (int i = 0; i < A.Length; i++)
            {
                Console.WriteLine(A[i]);
            }
 
            OrdenarPorNombre(A);
            Console.WriteLine();
            Console.WriteLine("Orden por nombre");
            for (int i = 0; i < A.Length; i++)
            {
                Console.WriteLine(A[i]);
            }
 
            Console.ReadLine();
 
        }

Si quieres, descarga este código para probarlo.

OPTIMIZACIONES

Hay muchas variantes del método de la burbuja, pero prácticamente ninguna logra resultados espectaculares.

No obstante, sí hay una que merece especial mención, ya que logra mejorar la eficiencia en el mejor caso y en casos promedio.

Esta optimización deriva del hecho de que en las últimas pasadas del algoritmo, es posible que el array ya esté ordenado y sin embargo el algoritmo no se pueda dar cuenta. Nos pasaba en el ejemplo de la primera página y también en el ejemplo del vídeo con las cartas.

Pues bien, si en una pasada no se realiza ningún intercambio, significa que ningún elemento está fuera de orden con respecto al siguiente... conclusión: el array ya está en orden y el algoritmo puede parar porque si en una pasada no se han hecho intercambios tampoco va a haber en las pasadas siguientes.

Con esta mejora, la eficiencia en el mejor caso se reduce a una sola pasada (Ω(n)), y en muchos casos, se puede parar antes, con lo que también se mejora en un caso promedio.

¿Y como se hace eso? ¿Metemos un if con un break dentro de los bucles for? ¡Desde luego que no! Los bucles for no están pensados para ser interrumpidos bruscamente. Los bucles que salen mediante una condición son while o do-while. En este caso, como necesitamos hacer siempre al menos una pasada utilizaremos un do-while.

En pseudocódigo podría quedar algo así:

algoritmo burbuja( A : array de n elementos indizados de 1 a n)
  boolean intercambios=false;
  entero i=1;
  hacer
       intercambios=false;
       para j desde 1 hasta n-i hacer: //el recorrido
         si A[j] > A[j+1] entonces //Si no están en orden
           intercambiar A[j] y  A[j+1] //Se intercambian
           intercambios=true
       fin para
       i=i+1
  mientras (intercambios AND i<=n-1)
fin algoritmo

Lo que adaptado a C# sería algo como esto:

static void BurbujaEnteros(int[] A)
        {
            int n = A.Length;
            int iaux;
            int i=1;
            bool intercambios;
            do
            {
                intercambios = false;
                for (int j = 1; j <= n - i; j++)
                {
                    if (A[j - 1] > A[j])
                    {
                        iaux = A[j - 1];
                        A[j - 1] = A[j];
                        A[j] = iaux;
                        intercambios = true;
                    }
                }
                i++;
            } while (intercambios && i <= n - 1);
        }