Bubble-sort

(S'ha redirigit des de: Ordenació de bombolla)

El Bubble Sort (ordenació de bombolla, en català) és un senzill algorisme d'ordenació. Funciona revisant cada element de la llista a ordenar amb el següent, intercanviant-de posició si estan en l'ordre equivocat. Cal revisar diverses vegades tota la llista fins que no es necessitin més intercanvis, la qual cosa significa que la llista està ordenada. Aquest algorisme obté el seu nom de la forma amb la que pugen per la llista els elements durant els intercanvis, com si fossin petites "bombolles". També és conegut com el mètode d'intercanvi directe. Se'l considera un algorisme de comparació, atès que només fa servir comparacions per ordenar els elements, sent el més senzill d'implementar.

Representació animada d'ordenació d'un conjunt de nombres amb l'algoritme de la bombolla. Començant des de l'inici de l'arranjament, es compara cada parell d'elements adjacents. Si tots dos no estan ordenats (el segon és menor que el primer), s'intercanvien les seves posicions. A cada iteració, un element menys necessita ser avaluats (l'últim), ja que no hi ha més elements a la seva dreta que necessitin ser comparats, atès que ja estan ordenats.
Bubble sort color editat
Bubble sort color editat

Descripció modifica

Una manera simple d'expressar l'ordenació de bombolla en pseudocodi és la següent:

 
 
 
 
 
 
 
 
 
 
 

Aquest algorisme realitza l'ordenació d'una llista a de n valors, en aquest cas de n termes numerats de l'0 als i n-1, consta de dos bucles niats, un amb l'índex i, que dona una grandària menor al recorregut de la bombolla en sentit invers de 2 a n, i un segon bucle amb l'índex j, amb un recorregut des 0 fins n-i, per a cada iteració del primer bucle, que indica el lloc de la bombolla.

La bombolla són dos termes de la llista seguits, j i j+1, que es comparen: si el primer és menor que el segon els seus valors s'intercanvien.

Aquesta comparació es repeteix al centre dels dos bucles, donant lloc fet i fet a una llista ordenada, es pot veure que el nombre de repeticions sola depèn de n, i no de l'ordre dels termes, és a dir, si passem a l'algorisme una llista ja ordenada, realitzarà totes les comparacions exactament igual que per a una llista no ordenada, aquesta és una característica d'aquest algorisme, després veurem una variant que evita aquest inconvenient.

Per comprendre el funcionament, vegem un exemple senzill:

Tenim una llista de nombres que cal ordenar:

 
 

Podem veure que la llista que té cinc termes, després:

 

L'índex i farà un recorregut de 2 fins n :

 

Que en aquest cas serà de 2 a 5. Per a cada un dels valors de i, j prengués successivament els valors de 0 fins n-i :

 

Per a cada valor de j, obtingut en aquest ordre, es compara el valor de l'índex j amb el següent:

 

Si l'acabo j és major que el terme j+1, els valors es permuten, en cas contrari es continua amb la iteració.

 

Per al cas de l'exemple, hem de:

 

Per a la primera iteració del primer bucle:

 

i j prengués els valors de 0 fins a 3 :

 

Quan j val 0, es comparen  , el 55 i el 86, ja que 55 <86 no es permuten l'ordre.

Ara j val 1 i es comparen   el 86 i el 48 Com 86> 48, es permuten, donant lloc a una nova llista.

Es repeteix el procés fins que j valgui 3, donant lloc a una llista parcialment ordenada, podem veure que el terme de major valor està en el lloc més alt.

 

Ara i val 3, i j farà un recorregut de 0 a 2.

Primer j val 0, es comparen  , el 55 i el 48, com 55> 48 es permuten donant lloc a la nova llista.

Per j = 1 es compara el 55 amb el 16 i es canvien d'ordre.

Per j = 2 es compara el 55 i el 82 i es deixen com estan, finalitzant el bucle amb una llista millor ordenada, es pot veure que els dos valors més alts ja ocupen el seu lloc. No s'ha realitzat cap comparació amb el terme quart, atès que ja se sap que després del primer cicle és el major de la llista.

L'algorisme consisteix en comparacions successives de dos termes consecutius, ascendint de baix a dalt en cada iteració, com l'ascensió de les bombolles d'aire a l'aigua, d'aquí el nom del procediment. En la primera iteració el recorregut ha estat complet, en el segon s'ha deixat ell últim terme, en tenir ja el més gran dels valors, en els successius sé ira deixant de realitzar les últimes comparacions, com es pot veure.

 

Ara ja i val 4 i j recorrerà els valors de 0 a 1.

Quan j val 0, es comparen   és a dir el 48 i el 16, ja que 48 és més gran que 16 es permuten els valors, donant lloc a una llista una mica més ordenada que l'anterior, des d'aquesta nova ordenació, j passa a valer 1, de manera que es comparen els termes   el 48 i el 55 que queden en el mateix ordre.

En aquest cas la bombolla ha ascendit menys que en els casos anteriors, i la llista aquesta ja ordenada, però l'algorisme haurà de completar-se, realitzant una última iteració.

Cal tenir en compte que el bucle per realitza un nombre fix de repeticions i per finalitzar hauran de completar-se, fins i tot en el cas extrem, que la llista estaria prèviament ordenada.

Finalment i val 5 i j només pot val 0, de manera que només es realitzés una comparació de   el 16 i el 48, que ja estan ordenats i es deixen igual.

 

Els bucles finalitzen i també el procediment, deixant la llista ordenada.

Una variant que finalitza en cas que la llista aquest ordenada, pot ser la següent: emprant un sentinella ordenat, que detecta que no s'ha modificat la llista en un recorregut de la bombolla, i que per tant la llista ja està ordenada, finalitzant.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Anàlisi modifica

 
Exemple de l'ordenació de bombolla ordenant una llista de nombres aleatoris.

Rendiment de l'algorisme modifica

A l'algorisme de la bombolla, per ordenar un vector de n termes, ha de realitzar sempre el mateix nombre de comparacions:

 

És a dir, el nombre de comparacions c(n) no depèn de l'ordre dels termes, sinó del nombre de termes.

 

Per tant la cota ajustada asimptòtica del nombre de comparacions pertany a l'ordre de n quadrat.

El nombre d'intercanvis i(n), que cal realitzar depèn de l'ordre dels termes i podem diferència, el cas millor, si el vector aquesta prèviament ordenat, i el cas pitjor, si el vector està ordenat en ordre invers.

 

Pel que no es pot determinar una cota ajustada asimptòtica del nombre d'intercanvis, ja que aquest dependrà de l'ordre del vector en qüestió.

Rendiment en el cas desfavorable modifica

Si passem a l'algorisme un vector ordenat en ordre invers realitzés un nombre de comparacions:

 

Com ja hem dit anteriorment, i haurà de realitzar un nombre igual d'intercanvis entre els termes del vector, ja que en cada comparació els termes estaran desordenats, i es realitzarà l'intercanvi.

 

Per tant en el cas més desfavorable tant el nombre de comparacions com el d'intercanvis coincideixen:

 

El nombre de comparacions o d'intercanvis en el cas més desfavorable pertany a l'ordre de n quadrat.

Rendiment en casos òptims modifica

En el cas òptim, el més favorable, és l'ordenació que un vector ja ordenat, en aquest cas el nombre de comparacions serà el mateix que en qualsevol altre cas:

 

La cota inferior asimptòtica del nombre de comparacions pertany a l'ordre de n quadrat, com en els altres casos, però en totes les comparacions l'ordre és el correcte i per tant no es realitza cap intercanvi:

 

Per tant el cost d'intercanvis no depèn de n, i és constant:

 

L'ordenació de bombolla té una complexitat Ω (n ²) com ordenació per selecció. Quan una llista ja està ordenada, a diferència del ordenació per inserció que passarà per la llista una vegada i trobareu que no hi ha necessitat d'intercanviar les posicions dels elements, el mètode d'ordenació per bombolla està forçat a passar per aquestes comparacions, el que fa que la seva complexitat sigui quadràtica en el millor dels casos. Això ho cataloga com l'algorisme més ineficient que existeix, encara que per a molts programadors sigui el més senzill d'implementar.

Conills i Tortugues modifica

La posició dels elements en l'ordenació de bombolla tenen un paper molt important en la determinació del rendiment. Els elements majors més al principi de la llista són ràpidament moguts cap avall, mentre els elements menors en el fons de la llista es mouen a la part superior molt lentament. Això va portar a nomenar aquests elements conills i tortugues , respectivament.

Diversos esforços s'han realitzat per a eliminar les tortugues vegeu Exterminació i millorar la velocitat de l'ordenació de bombolla, la qual serà més rodona que mai. L'ordenació per sacsejada és un bon exemple, tot i que encara manté, en el pitjor dels casos, una complexitat O (n 2 ) . L'ordenació per combinació compara els elements primer a trossos grans de la llista, movent tortugues extremadament ràpid, abans de procedir a trossos cada vegada més petits per allisar la llista. La seva velocitat mitjana és comparable a algorismes ràpids (i complexos) com el Quicksort.


A la pràctica modifica

Tot i que l'ordenació de bombolla és un dels algorismes més senzills d'implementar, el seu ordre O (n 2 ) ho fa molt ineficient per fer servir en llistes que tinguin més que un nombre reduït d'elements. Fins i tot entre els algorismes d'ordenació d'ordre O (n 2 ) , altres procediments com l'ordenació per inserció són considerats més eficients.

Donada la seva simplicitat, l'ordenació de bombolla és utilitzat per introduir el concepte d'algorisme d'ordenació per a estudiants de ciències de la computació. Malgrat això, alguns investigadors com Owen Astrachan han criticat la seva popularitat en l'ensenyament de ciències de la computació, arribant a recomanar la seva eliminació dels plans d'estudi.[1]

Sumat a això, Jargon File, un llibre àmpliament citat en la cultura dels furoners, l'anomena «el mal algorisme genèric», i Donald Knuth, un dels majors experts en ciències de la computació, afirma que l'ordenació de bombolla «no sembla tenir res per recomanar el seu ús, a excepció d'un nom enganxós i el fet que comporta a problemes teòrics interessants».[2]

L'ordenació de bombolla és asimptòticament equivalent en temps d'execució amb l'ordenació per inserció en el pitjor dels casos, però tots dos algorismes difereixen principalment en la quantitat d'intercanvis que són necessaris. Resultats experimentals com els descoberts per Astrachan han demostrat que l'ordenació per inserció funciona considerablement millor fins i tot amb llistes aleatòries. Per aquesta raó, molts llibres d'algorismes moderns eviten utilitzar l'ordenació de bombolla, reemplaçant-ho per l'ordenació per inserció.

L'ordenació de bombolla interacciona vagament amb el maquinari de les CPU modernes. Requereix almenys el doble d'escriptures que l'ordenació per inserció, el doble de pèrdues de memòria cau, i asimptòticament més predicció de salts. Diversos experiments d'ordenació de cadenes en Java fets per Astrachan mostren que l'ordenació de bombolla és 5 vegades més lent que l'ordenació per inserció, i 40% més lent que l'ordenació per selecció.[1]

Exemple pas a pas modifica

Prenguem com a exemple els números:: "9 6 5 8 2 1", que seran ordenats de forma ascendent utilitzant el mètode de la bombolla.

Els elements ressaltats estan sent comparats.

Primera volta: (9 6 5 8 2 1)   (6 9 5 8 2 1), l'algorisme compara els primers dos elements i els canvia perquè 9> 6 (6 9 5 8 2 1)   (6 5 9 8 2 1) (6 5 9 8 2 1)   (6 5 8 9 2 1) (6 5 8 9 2 1)   (6 5 8 2 9 1) (6 5 ona 9 1)   (6 5 8 2 1 9)

Segona volta: (6 5 8 2 1 9)   (5 6 8 2 1 9) (5 6 8 2 1 9)   (5 6 8 2 1 9), com aquests elements ja estan ordenats, l'algorisme no fa canvis. (5 6 8 2 1 9)   (5 6 2 8 1 9) (5 6 2 8 1 9)   (5 6 2 1 8 9) (5 6 2 1 8 9)   (5 6 2 1 8 9)

Tercera volta: (5 6 2 1 8 9)   (5 6 2 1 8 9) (5 6 2 1 8 9)   (5 2 6 1 8 9) (5 2 6 1 8 9)   (5 2 1 6 8 9) (5 2 1 6 8 9)   (5 2 1 6 8 9) (5 2 1 6 8 9)   (5 2 1 6 8 9)

Quarta volta: (5 2 1 6 8 9)   (2 5 1 6 8 9) (2 5 1 6 8 9)   (2 1 5 6 8 9) (2 1 5 6 8 9)   (2 1 5 6 8 9) (2 1 5 6 8 9)   (2 1 5 6 8 9) (2 1 5 6 8 9)   (2 1 5 6 8 9)

Cinquena volta: (2 1 5 6 8 9)   (1 2 5 6 8 9) (1 2 5 6 8 9)   (1 2 5 6 8 9) (1 2 5 6 8 9)   (1 2 5 6 8 9) (1 2 5 6 8 9)   (1 2 5 6 8 9) (1 2 5 6 8 9)   (1 2 5 6 8 9)

Exemple en C++ modifica

Aquest és un exemple d'un programa que demana números i els ordena de forma ascendent i descendent en llenguatge C++, compilat amb g++ 5.4.0

// ORDENACIÓ DE NOMBRES MITJANÇANT L'ALGORITME BUBBLE SORT. OMAR BRIQA

#include<iostream>

using namespace std;

int main(){
	
	double num[1000], aux;
	int n;
	
		cout << "\nQuants nombres vol ordenar: ";
		cin >> n;	
	
		cout << "\n\nEscrigui els nombres que vol ordernar\n" << endl;
			
			for (int i = 0; i < n; i++){
				
				cin >> num[i];
				
			}
		
		// ALGORITME DE BOMBOLLA
			
			for (int i = 0; i < n; i++){
								
				for (int j = 0; j < (n-1); j++){
				
					if (num[j] > num[j+1]){ // SI EL NOMBRE ANTERIOR ÉS MES GRAN QUE EL POSTERIOR
						
						aux = num[j];
						num[j] = num[j+1];
						num[j+1] = aux;	
						
						// INTERCANVI DE VALORS MENTRE NO ES COMPLEIXI LA CONDICIÓ
					}
			
				}
					
			}

			
		cout << "\nLa llista dels nombres ordenats de forma ascendent es: \n" << endl;	
					
			for (int i = 0; i < n; i++){
				
				cout << num[i] << " ";
				
			}	
			
		cout << "\n\nLa llista dels nombres ordenats de forma descendent es: \n" << endl;	
					
			for (int i = (n-1); i >= 0; i--){
				
				cout << num[i] << " ";
				
			}
			
		cout << "\n" << endl;	
	
	system("pause");
	return 0;
}

Exemple en Python3 modifica

def bubbleSort(array):
 n = len(array)

 for i in range(n):
 for j in range(0, n-1):
 if array[j] > array[j+1]:
 array[j], array[j+1] = array[j+1], array[j]

array = [200 ,190, 1200, 1, 2, 4, 55, 1000, 6, 800]
bubbleSort(array)

print(array)

Vegeu també modifica

Referències modifica

  1. 1,0 1,1 «onada/papers/bubble.pdf ordenació de bombolla: Un analistes arqueològic d'un algorisme» (en anglès). SIGCSE, 2003 [Consulta: 9 març 2011].
  2. Knuth, Donald. «5.2.2: ordenació per intercanvi». A: L'art de programar ordinadors, Volum 3 (en anglès). segon. Addison-Wesley, 1998, p. 106-110. ISBN 0-201 - 89.685-0 [Consulta: 9 març 2011]. 

Enllaços externs modifica

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Bubble-sort