Bubble-sort bidireccional

De Viquipèdia
Dreceres ràpides: navegació, cerca
Exemple de l'operativa pas a pas

L' ordenació de bombolla bidireccional ( cocktail sort en anglès) és un algorisme d'ordenació que sorgeix com una millora de l'algorisme ordenació 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 l'algorisme segueix sent O ( n ²).

Exemples de codi[modifica | modifica el codi]

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

Procediment Ordenacion_Sacudida (v: vector, també: sencer)
Variables
i, j, esq, der, últim: tipoposicion;
aux: tipoelemento;
Inici
//Límits superior i inferior d'elements ordenats
esq <- 2
der <- també
últim <- també

Repetir
//Bombolla cap a l'esquerra}
//Els valors menors van a l'esquerra
Per i <- der fins esq fer
Si v (i-1)> v (i) llavors
aux <- v (i)
v (i) <- v (i-1)
v (i-1) <- aux
últim <- i
Fin_si
Fin_para

esq <- últim+1

//Bombolla cap a la dreta
//Els valors més grans van a la dreta
Per j <- esq fins der fer
Si v (j-1)> v (j) llavors
aux <- v (j)
v (j) <- v (j-1)
v (j-1) <- aux
últim <- j
Fin_si
Fin_para

der <- últim-1

Fins (esq> der)
Fi

Aquí es mostra la seva implementació en Java:

public class CocktailSort{
 
 public static int esquerra, dreta, últim;//variables per ordenació
 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 = arreglo.length;
 últim = arreglo.length-1;
 
 do{
 for (int i = arreglo.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;
 últim = i;
 }
 }
 esquerra = últim+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 = últim-1;
 }While (dreta> = esquerra);
 
 for (int i = 0; i <arreglo.length; i++){
 System.out.println (acord [i]);
 }
}

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. Gopal. Magnifying Data Structures. PHI Learning Pvt. Ltd., p. 392–. ISBN 978-81-203-4019-0 [Consulta: 28 desembre 2012]. 

Enllaços externs[modifica | modifica el codi]