Ordenamiento de burbuja bidireccional

El ordenamiento de burbuja bidireccional (cocktail sort en inglés) es un algoritmo de ordenamiento que surge como una mejora del algoritmo ordenamiento de burbuja.

La manera de trabajar de este algoritmo es ir ordenando al mismo tiempo por los dos extremos del vector. De manera que tras la primera iteración, tanto el menor como el mayor elemento estarán en sus posiciones finales. De esta manera se reduce el número de comparaciones aunque la complejidad del algoritmo sigue siendo O(n²).

A continuación se muestra el pseudo-código del algoritmo:

 Procedimiento Ordenacion_Sacudida (v:vector, tam:entero) 
 Variables
   i, j, izq, der, ultimo: tipoposicion;
   aux: tipoelemento;
 Inicio
   //Limites superior e inferior de elementos ordenados
   izq <- 2
   der <- tam
   ultimo <- tam
 
   Repetir
     //Burbuja hacia la izquierda}
     //Los valores menores van a la izquierda
     Para i <- der hasta izq hacer
         Si v(i-1) > v(i) entonces
             aux <- v(i)
             v(i) <- v(i-1)
             v(i-1) <- aux
             ultimo <- i
         Fin_si
     Fin_para
     
     izq <- ultimo+1
 
     //Burbuja hacia la derecha
     //Los valores mayores van a la derecha
     Para j <- izq hasta der hacer
         Si v(j-1) > v(j) entonces
             aux <- v(j)
             v(j) <- v(j-1)
             v(j-1) <- aux
             ultimo <- j
         Fin_si
     Fin_para
 
     der <- ultimo-1
 
   Hasta (izq > der)
 Fin

Aquí se muestra su implementación en Java:

public class CocktailSort {
 
    public static int izquierda,derecha,ultimo;  //variables para ordenamiento
    public static int arreglo[] = {10,23,6,4,223,2,112,3,6,34}; // predefino arreglo
 
    public static void main(String[] args) {
 
    izquierda = 1;
    derecha = arreglo.length;
    ultimo = arreglo.length-1;
 
    do{
        for(int i=arreglo.length-1;i>0;i--){
            //Burbuja hacia la izquierda
            //Los valores menores van a la izquierda 
            if(arreglo[i-1] > arreglo[i]){
                int aux = arreglo[i]; // variable auxiliar para poder hacer intercambio de
                arreglo[i] = arreglo[i-1];  // posicion
                arreglo[i-1] = aux;
                ultimo = i;
            }
        }
        izquierda = ultimo+1;
        for(int j=1;j<arreglo.length;j++){
            if(arreglo[j-1] > arreglo[j]){
                int aux = arreglo[j];
                arreglo[j] = arreglo[j-1];
                arreglo[j-1] = aux;
                ultimo = j;
            }
        }
        derecha = ultimo-1;
    }while(derecha >= izquierda);
 
    for(int i=0;i<arreglo.length;i++){
        System.out.println(arreglo[i]);
    }
}

Enlaces externos

• Ordenamiento por Sacudida en Python