Cocktail-sort

L'ordenament de bombolla bidireccional ( cocktail sort en anglès) és un algorisme d'ordenament que sorgeix com una millora de l'algorisme ordenament de bombolla.

La manera de treballar d'aquest algorisme és anar ordenant al mateix temps pels dos extrems del vector. De manera que després de la primera iteració, tant el menor com el major element estaran en les seves posicions finals. D'aquesta manera es redueix el nombre de comparacions encara que la complexitat de l'algorisme segueix sent O ( n ²).

Exemples de codi

A continuació es mostra el pseudocodi de l'algorisme:

 Procediment CocktailSort (v:vector, tam:enter) 
 Variables
   i, j, esq, dre, ultim: tipusposicio;
   aux: tipuselement;
 Inici
   //Límits superior i inferior d'elements ordenats
   esq <- 2
   dre <- tam
   ultim <- tam
 
   Repetir
     //Bombolla cap a l'esquerra}
     //Els valors menors s'ordenen a l'esquerra
     //dre es va disminuint en 1 fins arribar a esq
        Per i <- der fins esq fer
         Si v(i-1) > v(i) aleshores
             aux <- v(i)
             v(i) <- v(i-1)
             v(i-1) <- aux
             ultim <- i
         Fi_si
     Fin_per
     
     esq <- ultim+1
 
     //Bombolla cap a la dreta
     //Els valors majors s'ordenen a la dreta
     Per j <- esq fins que dre
         Si v(j-1) > v(j) aleshores
             aux <- v(j)
             v(j) <- v(j-1)
             v(j-1) <- aux
             ultim <- j
         Fi_si
     Fi_per
 
     dre <- ultim-1
 
   fins (esq > dre)
 Fi

Aquí es mostra la seva implementació en Java:

public class CocktailSort{
 
    public static int esquerra, dreta, últim;//variables per ordenament
    public static int acord [] ={10,23,6,4,223,2,112,3,6,34};//predefineix acord
 
    public static void main(String[] args) {
 
    esquerra = 1;
    dreta = acord.length;
    ultim = acord.length-1;
 
    do{
        for(int i = acord.length-1; i> 0; i -){
            //Bombolla cap a l'esquerra
            //Els valors menors van a l'esquerra
            if(acord [i-1]> acord [i]){
                int aux = acord [i];//variable auxiliar per poder fer intercanvi de
                acord [i] = acord [i-1];//posició
                acord [i-1] = aux;
                ultim = i;
            }
        }
        esquerra = ultim+1;
        for(int j = 1; j <arreglo.length; j++){
            if(acord [j-1]> acord [j]){
                int aux = acord [j];
                acord [j] = acord [j-1];
                acord [j-1] = aux;
                últim = j;
            }
        }
        dreta = ultim-1;
    }while(dreta >= esquerra);
 
    for(int i = 0; i < acord.length; i++){
        System.out.println(acord [i]);
    }
}

Vegeu també

• Bubble-sort

Enllaços externs

• Dictionary of Algorithms and Data Structures del NIST (anglès)
• Comparativa de diferents algorismes d'ordenació (anglès)