6.1.1 Ordenacion Burbuja

El método de intercambio directo, conocido coloquialmente como burbuja, es el utilizado entre los estudiantes principiantes de computación por su fácil comprensión y programación. Pero es preciso señalar que es quizás el método más ineficiente.

El método de intercambio directo puede trabajar de dos maneras diferentes: llevando los elementos más pequeños hacia la parte izquierda del arreglo o trasladando elementos más grandes hacia su parte derecha. La idea básica de este algoritmo con en comparar pares de elementos adyacentes e intercambiarlos entre si hasta que los elementos se encuentren ordenados. Se realizan (n - 1) pasadas transportando en cada una de el menor o mayor de elementos según sea el caso a su position ideal. Al final 1 (n - 1) pasadas los elementos del arreglo estarán ordenados.

Ejemplo. Supongamos que se desea ordenar las siguientes claves del arreglo unidimensional A, transportando en cada pasada el menor elemento hacia la parte izquierda del arreglo.

A: 15    67    08    16   44   27    12   35

Las comparaciones que se realizan son:

PRIMERA PASADA

• A[7]  >  A[8]      (12 > 35)       no hay intercambio
• A[6]  >  A[7]      (27 > 12)       si hay intercambio
• A[5]  >  A[6]      (44 > 12)       si hay intercambio
• A[4]  >  A[5]      (16 > 12)        si hay intercambio
• A[3]  >  A[4]      (08 > 12)       no hay intercambio
• A[2]  >  A[3]      (67 > 08)       si hay intercambio
• A[1]  >  A[2]      (15 > 08)       si hay intercambio

Luego de la primera pasada el arreglo queda así:

A: 08   15    67    12    16   44   27    35

Observe que el elemento más pequeño, en este caso 08, fue situado en izquierda del arreglo.

SEGUNDA PASADA

• A[7]  >  A[8]    (27 > 35)       no hay intercambio
• A[6]  >  A[7]    (44 > 27)       si hay intercambio
• A[5]  >  A[6]    (16 > 27)       no hay intercambio
• A[4]  >  A[5]    (12 > 16)        no hay intercambio
• A[3]  >  A[4]    (67 > 12)        si hay intercambio
• A[2]  >  A[3]    (15 > 12)        si hay intercambio

Luego de la segunda pasada el arreglo queda así:

A:  08   12    15    67    16    27    44    35

y el segundo elemento más pequeño del arreglo, en este caso 12, fue situado en la segunda position.

El algoritmo de ordenación por el método de intercambio directo que transporta en cada pasada el menor elemento hacia la parte izquierda del arreglo es el siguiente:

Burbuja menor (A, N)

Este algoritmo ordena los elementos del arreglo unidimensional utilizando el método de la burbuja. Transporta en cada pasada el elemento más pequeño hacia la parte izquierda del arreglo. A es un arreglo unidimensional de N elementos I, J y AUX son variables de tipo entero

1. Repetir con I desde 2 hasta  N
     1.1  Repetir con J desde N hasta I
          1.1.1 Si A(J - 1) > A[J] entonces
                      Hacer AUX <- A[J - 1], A[J - 1] <- A[I] y A[I] <- AUX 
          1.1.2 Fin del condicional del paso 1.1.1
     1.2 Fin del ciclo del paso 1.1
2. Fin del ciclo del paso 1

Otra versión es hacer que el algoritmo de ordenación por el método de intercambio directo que transporta a cada pasada el elemento mayor hacia la parte derecha del arreglo es:

Burbuja mayor (A, N)   

El algoritmo ordena los elementos del arreglo unidimensional A. Transporta en cada pasada el elemento más grande hacia la parte derecha del arreglo. A es un arreglo de N elementos) I, J y AUX son variables de tipo entero   

1. Repetir con I  desde N-l hasta 1
     1.1. Repetir con J desde 1 hasta I
          1.1.1. Si A[J]  > A [J + 1] entonces
                          Hacer AUX <- A[J], A[J] <- A[J + 1] y A[J + 1] <- AUX
          1.1.2. Fin del condicional del paso 1.1.1       
     1.2. Fin del ciclo del paso 1.1
2. Fin del ciclo del paso 1

Análisis de eficiencia del método de intercambio directo

El número de comparaciones que se realizan en el método de la burbuja se puede contabilizar fácilmente. En la primera pasada se realizan (n - 1) comparaciones, en la segunda pasada (n - 2)comparaciones, en la tercera pasada (n - 3) comparaciones y así sucesivamente hasta llegar a 2 y 1 comparaciones entre claves, siendo n el número de elementos del arreglo. Por lo tanto, tenemos que el numero de comparaciones es:

Que es igual a =

Como ya se mencionado, se hace uso del principio de inducción matemática para desarrollar ciertas formulas.

Respecto del nmero de movimientos, estos dependen fundamentalmente de si el arreglo se encuentra ordenado, desordenado o en orden inverso. Los movimientos para cada uno de estos casos son:

  

Ahora bien, el tiempo necesario para ejecutar el algoritmo de la burbuja es proporcional a n^2 , O(n2), donde n es el número de elementos del arreglo.

Ejemplo en C

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;
               }
          }
     }
}