Vés al contingut

Cocktail-sort

De la Viquipèdia, l'enciclopèdia lliure
(S'ha redirigit des de: Cocktail sort)
Exemple de l'operativa pas a pas

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

[modifica]

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é

[modifica]

Referències

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

Enllaços externs

[modifica]