Ordenamiento de burbuja bidireccional

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

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


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Algoritmo de ordenamiento — Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por …   Wikipedia Español

  • Comb sort — En ciencias de la computación, el comb sort es un algoritmo de ordenamiento relativamente simple diseñado por Wlodzimierz Dobosiewicz en 1980. Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo… …   Wikipedia Español

  • Gnome sort — El algoritmo de ordenación conocido como gNome sort tiene una historia de invención cuasi paralela. Durante un tiempo existió la polémica sobre su invención, finalmente atribuída a Hamid Sarbazi Azad quien lo desarrolló en en año 2000 y al que… …   Wikipedia Español

  • Edad Contemporánea — La carga de los mamelucos, de Francisco de Goya, 1814, representa un episodio del levantamiento del 2 de mayo de 1808 en Madrid. Los pueblos europeos, convertidos en protagonistas de su propia historia y a los que se les había proclamado sujetos… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”