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.

Ejemplo de la operativa paso a paso

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²).

Hacemos un recorrido ascendente (del primer elemento al último), cogemos el primer elemento y lo comparamos con el siguiente, si el siguiente es menor lo pasamos al puesto anterior, de esta forma al final de la lista nos queda el mayor. Una vez terminada la serie ascendente, hacemos un recorrido descendente (del último elemento al primero) pero esta vez nos quedamos con los menores a los que vamos adelantando posiciones en vez de retrasarlas como hicimos en la serie ascendente. Repetimos las series alternativamente pero reduciendo el ámbito en sus extremos pues ya tendremos allí los valores más bajos y más altos de la lista, hasta que no queden elementos en la serie; en el pseudocódigo de ejemplo: Hasta (izq > der).

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

 Procedimiento Ordenacion_Sacudida (v:vector, tam:entero)  Variables   i, j, izq, der, último: tipoposicion;   aux: tipoelemento; Inicio   //Límites superior e inferior de elementos ordenados   izq <- 2   der <- tam   último <- tam    Repetir     //Burbuja hacia la izquierda}     //Los valores menores van a la izquierda     //der va disminuyendo en 1 hasta llegar a izq        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             último <- i         Fin_si     Fin_para          izq <- último+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             último <- j         Fin_si     Fin_para      der <- último-1    Hasta (izq > der) Fin
Other Languages