Ordenación de burbujas

La ordenación por burbujas también se conoce como Sinking Sort. Es un algoritmo de ordenación simple que recorre repetidamente la lista que hay que ordenar, comparando cada par de elementos adyacentes y los intercambia si están en el orden equivocado.

Este procedimiento se repite hasta que no se realicen intercambios.

Como al menos un elemento se mueve a su lugar final en cada pasada, podemos decrementar la última posición comprobada en cada pasada.

La siguiente animación muestra cómo funciona la ordenación por burbujas:

1. void bubble_sort(int* lst, int size)
2. {
3.     int pass = 0;
4.     int swapped = 1;
5.     int current;
6.     while (swapped) {
7.         swapped = 0;
8.         pass ++;      
9.         for (current=0;current<size-pass;current++) {
10.         if (lst[current]>lst[current+1]){
11.             swapped = 1;
12.             int temp = lst[current];
13.             lst[current] = lst[current+1];
14.             lst[current+1] = temp;
15.         }
16.         }
17.     }
18. }

1. def bubble_sort(lst):
2.   swapped = True
3.   num_pass = 0
4.   while swapped == True:
5.     swapped = False
6.     num_pass = num_pass + 1
7.     for current in range(0, len(lst) - num_pass):
8.       if (lst[current] > lst[current + 1]):
9.         swapped = True
10.         lst[current], lst[current + 1] = lst[current + 1],lst[current]
11.   return lst

1. type tab = array[1..20] of integer;
2. procedure bubble_sort(var lst : tab);
3.    
4. var swapped : boolean;
5.     current : integer;
6.     temp : integer;
7.     pass : integer;
8.      
9. begin
10.   pass := 1;
11.   REPEAT
12.     swapped := false;
13.     for current := 1 to 20 - pass do
14.     begin
15.     if (lst[current] > lst[current + 1]) then
16.     begin
17.         { on échange les deux éléments }
18.         temp := lst[current];
19.         lst[current]:=lst[current + 1];
20.         lst[current + 1]:=temp;
21.         swapped := true;
22.     end;
23.     end;
24.     pass := pass + 1;
25.     UNTIL (not swapped);
26. end;

1. let swap a b t =
2.     let temp = t .( b ) in t .( b ) <- t .( a ) ; t .( a ) <- temp ;;
3.  
4. let bubble_sort vect =
5.     let length = Array.length vect in
6.         for max_pos = length - 1 downto 0 do
7.             for current = 0 to max_pos - 1 do
8.                 if vect.( current ) > vect.( current + 1 ) then swap current ( current + 1 ) vect
9.             done;
10.         done;
11.     vect;
12. ;;

Trabajo práctico

El minijuego que se presenta a continuación permite intentar clasificar, en orden de peso creciente, 5 barriles, con una balanza Roberval para compararlos. Puedes intentar resolverlo con el método de clasificación por burbujas.

Variations

La versión original de Donald Knuth es un poco más sencilla, pero la idea es la misma: comparamos elementos adyacentes y los intercambiamos si es necesario.

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void bubble_sort(int* lst, int size) {
    for(int i=size-1; i > 0; i--)
        for(int j=0; j < i;j++)
            if (lst[j+1] < lst[j]){
                swap(&lst[j],&lst[j+1]);
            }
}

Sin embargo, este código tiene la desventaja de que siempre realiza el mismo número de operaciones, independientemente de la matriz de entrada. La siguiente implementación se detiene en cuanto ha realizado una ejecución sin ninguna permutación. Esta es la más común hoy en día.

Todavía podemos mejorarlo un poco porque, si en una iteración el último intercambio se hizo en la posición N, entonces todos los elementos situados después de esta posición N están en el orden correcto. Así, para las siguientes iteraciones, es inútil volver a explorarlos. Tendríamos entonces algo así:

void bubble_sort1(int* lst, int size)
{
    int swapped = 1;
    int lastswap = size ;
    int j;
    while (swapped) {
        swapped = 0;
        for (j=0;j<lastswap - 1;j++) {
            if (lst[j]>lst[j+1]){
                swapped = j+1;
                swap(&lst[j],&lst[j+1]);
            }
        }
        lastswap = swapped;
    }
}

Complejidad

Desde el punto de vista educativo, este algoritmo es muy interesante. Es fácil de entender y, por tanto, también de explicar. Es fácil de codificar en la mayoría de los lenguajes informáticos y ofrece la posibilidad de manipular vectores o listas. Puede utilizarse como base para muchos ejercicios de optimización. Y tiene un nombre pegadizo.

Pero, en el mundo real, hay que decir que no es muy eficiente. A menudo se critica, incluso se considera “ingenua” y “debe evitarse absolutamente”. Sin embargo, tiene el mérito de ser suficientemente eficiente en listas pequeñas o en listas que ya están parcialmente ordenadas.

En el peor de los casos, con los datos ordenados en sentido inverso, las ejecuciones sucesivas de la tabla requieren (n² - n) / 2 intercambios. Por ejemplo, para una lista de 10 elementos, se necesitarán, en el peor de los casos, 45 comparaciones y 45 intercambios [ (10² - 10) / 2 ]. La complejidad es por tanto cuadrática, del orden O(n²).

Cuando el orden inicial de los elementos a clasificar es aleatorio, se considera que serán necesarios (n² - n) / 4 intercambios. Por lo tanto, la complejidad será también O(n²).

En el mejor de los casos, cuando la lista ya está ordenada, se necesitarán (n - 1) comparisons and no permutations. comparaciones y ninguna permutación. La complejidad es lineal, en O(n).

La animación siguiente permite comprobar, de forma empírica, esta evolución del número de operaciones en función del número de elementos a ordenar.

Para tener una idea más concreta del rendimiento de este algoritmo, suponga que tiene que ordenar alfabéticamente el directorio de los habitantes de varias grandes ciudades. Y que la máquina que tiene a su disposición puede realizar, digamos, diez millones de instrucciones por segundo . Se puede estimar el tiempo necesario para esta clasificación.