Bubble-sort
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-los 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 què 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, i és el més senzill d'implementar.
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 de 0 fins a 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 a fer un nombre fix de repeticions i per a finalitzar han 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 estigui 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]
Rendiment de l'algorisme
[modifica]L'algorisme de la bombolla, per a ordenar un vector de n termes, ha de fer 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 està 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, fa un nombre de comparacions:
Com ja hem dit anteriorment, i ha de fer 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 fa cap intercanvi:
Com a resultat, 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 de pressa, 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 Python 3
[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,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].
- ↑ 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]
- 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)
- Demostració de la seva implementació Arxivat 2008-02-19 a Wayback Machine.
- Bombolla bàsic i millorat en Python Arxivat 2013-08-12 a Wayback Machine.