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.[1]
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 a 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é
Referències
Enllaços externs
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
