Ordenamiento de burbuja bidireccional

Atención , esta página está siendo migrada a https://lwh-21.github.io/Algos/

El ordenamiento de burbuja bidireccional

El ordenamiento de burbuja bidireccional (también llamado "método de la sacudida" o "coctail sort" o "shaker sort") es un algoritmo de ordenamiento que surge como una mejora del algoritmo ordenamiento de burbuja.

Si ya habéis visto como funciona el algoritmo de ordenación por burbuja habréis observado que los números grandes se están moviendo rápidamente hasta al final de la lista (estas son las "liebres"), pero que los números pequeños (las "tortugas") se mueven sólo muy lentamente al inicio de la lista.

Una solución es de ordenar con el método de burbuja y cuando llegamos al final de la primera iteración, no volver a realizar el cálculo desde el principio sino que empezaremos desde el final hasta al inicio. De esta manera siempre se consigue que tanto los números pequeños como los números grandes se desplacen a los extremos de la lista lo más rápido posible.

Representación animada del algoritmo :

Representación animada del ordenamiento de burbuja bidireccional

  1. PROCEDIMIENTO cocktail_sort ( VECTOR a[1:n])
  2.  
  3. dirección ← 'frontal', comienzo ← 1, fin ← n-1, actual ← 1
  4.  
  5. REPETIR
  6.    permut ← FALSO
  7.    REPETIR
  8.        SI a[actual] > a[actual + 1] ENTONCES
  9.            intercambiar a[actual] Y a[actual + 1]
  10.            permut ← VERDADERO
  11.        FIN SI  
  12.        SI (dirección='frontal') ENTONCES
  13.            actual ← actual + 1
  14.        SI NO
  15.            actual ←actual - 1
  16.        FIN SI
  17.    MIENTRAS QUE ((dirección='frontal') Y (actual<fin)) OU ((dirección='final) O (actual>comienzo))
  18.    SI (dirección='frontal') ENTONCES
  19.        dirección ← 'final'
  20.        fin ← fin - 1
  21.    SI NO
  22.        dirección ← 'frontal'
  23.        comienzo ← comienzo + 1
  24.    FIN SI
  25. MIENTRAS permut = VERDADERO
  26.  
  27. FIN PROCEDIMIENTO
  1. let cocktail_sort vector =
  2.     let permutation = ref true and actual = ref 0 and dirección = ref 1
  3.     and comienzo = ref 0 and fin = ref ((Array.length vector) - 2)  in
  4.     while (!permutation = true) do
  5.         permutation := false;
  6.         while ((!dirección=1) && (!actual < !fin)) || ((!dirección = -1) && (!actual > !comienzo)) do
  7.             actual := !actual + !dirección;
  8.             if vector.(!actual) > vector.(!actual + 1) then
  9.             begin
  10.                 (* Intercambiamos los dos elementos *)
  11.                 permutation := true;
  12.                 let temp = vector.(!actual) in
  13.                 begin
  14.                    vector.(!actual) <- vector.(!actual + 1);
  15.                    vector.(!actual + 1) <- temp;
  16.                 end
  17.             end
  18.         done;
  19.         if (!dirección = 1) then fin := !fin - 1 else comienzo := !comienzo + 1;
  20.         dirección := - !dirección;
  21.     done;
  22. vector;;
  1. type tab = array[1..20] of integer;
  2. procedure cocktail_sort(var vector : tab);
  3.  
  4. var permutation : boolean;
  5.     actual, temp : integer;
  6.     dirección : integer;
  7.     comienzo,fin : integer;
  8.  
  9. begin
  10.     actual:=1;dirección:=1;
  11.     comienzo:=0;fin:=20;
  12.     REPEAT
  13.         permutation := false;
  14.         while ((actual<fin) and (dirección=1)) or
  15.         ((dirección=-1) and (actual>comienzo)) do
  16.         begin
  17.             actual:=actual+dirección;
  18.             if vector[actual]<vector[actual-1] then
  19.             begin
  20.                 temp:=vector[actual];
  21.                 vector[actual]:=vector[actual - 1];
  22.                 vector[actual - 1] := temp;
  23.                 permutation:=true;
  24.             end;
  25.         end;
  26.         if dirección=1 then fin:=fin - 1 else comienzo:=comienzo + 1;
  27.         dirección:=-dirección;
  28.     UNTIL (not permutation);
  29. end;
  1. def cocktail_sort(vector):
  2.     permutation,dirección,actual = True,1,0
  3.     comienzo,fin = 0,len(vector)-2
  4.     while permutation == True:
  5.         permutation = False
  6.         while (actual<fin and dirección==1) or \
  7.         (actual>comienzo and dirección==-1) :
  8.             # Prueba si intercambio
  9.             if vector[actual] > vector[actual + 1]:
  10.                 permutation = True
  11.                 # Intercambiamos los dos elementos
  12.                 vector[actual], vector[actual + 1] = \
  13.                 vector[actual + 1],vector[actual]
  14.             actual = actual + dirección
  15.         # Cambiar la dirección de desplazamiento
  16.         if dirección==1:
  17.             fin = fin - 1
  18.         else:
  19.             comienzo = comienzo + 1
  20.         dirección = -dirección
  21.     return vector  
  22.  
  1. typedef int bool;
  2. enum { false, true };
  3.  
  4. void cocktail_sort(int* vector) {
  5.     bool permutation;
  6.     int actual=0, dirección=1;
  7.     int comienzo=1, fin=19;
  8.     do {
  9.         permutation=false;
  10.         while (((dirección==1) && (actual<fin)) || ((dirección==-1) && (actual>comienzo))) {
  11.             actual += dirección;
  12.             if (vector[actual]<vector[actual-1]) {
  13.                 int temp = vector[actual];
  14.                 vector[actual]=vector[actual-1];
  15.                 vector[actual-1]=temp;
  16.                 permutation=true;
  17.             }
  18.         }
  19.         if (dirección==1) fin--; else comienzo++;
  20.         dirección = -dirección;
  21.     } while (permutation);
  22. }

Use este algoritmo para resolver el pequeño conjunto de la página anterior :



 


Los siguientes gráficos muestran el aumento en el número de transacciones en relación con el número de elementos a ser ordenados.

Rendimiento del algoritmo

En el caso óptimo, con los datos ya ordenados, el algoritmo sólo effectura n comparaciones. Por lo tanto la complejidad en el caso óptimo es en Θ(n).

Rendimiento en el caso óptimo Número de operaciones Número de términos Θ(n)

En el caso desfavorable, con los datos ordenados a la inversa, la complejidad es en Θ(n2).

Rendimiento en el caso desfavorable Número de operaciones Número de términos Θ(n2)

En el caso medio, la complejidad de este algoritmo es también en Θ(n2)

Rendimiento en el caso medio NNúmero de operaciones Número de términos Θ(n2)