Bubble-sort bidireccional
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
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 Fi_Si Fi_Per 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 Fi_Si Fi_Per 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 = acord.length; últim = 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 posició acord[i] = acord[i-1]; acord[i-1] = aux; últim = i; } } esquerra = últim+1; for (int j = 1; j < acord.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 < acord.length; i++){ System.out.println(acord[i]); } } }
Vegeu també
- Bubble-sort
Referències
- ↑ Gopal. Magnifying Data Structures. PHI Learning Pvt. Ltd., p. 392–. ISBN 978-81-203-4019-0 [Consulta: 28 desembre 2012].
Enllaços externs
- Dictionary of Algorithms and Data Structures del NIST (anglès)
- Comparativa de diferents algorismes d'ordenació Arxivat 2016-01-13 a Wayback Machine. (anglès)
- Ordenació per "burs" en Python Arxivat 2013-08-12 a Wayback Machine.