Bubble-sort

De Viquipèdia
Dreceres ràpides: navegació, cerca
Demostració-exemple de BubbleSort

El Bubble Sort (ordenació de bombolla, en anglès) é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.

Descripció[modifica | modifica el codi]

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


 {\color{Sepia}\mathit{procedure}} \;
 {\color{Blue}\mathit{BubbleSort}} \;
 (
 {\color{Black}\mathit{a}}
 {\color{Plum}\mathit{{}_0}} ,
 {\color{Black}\mathit{a}}
 {\color{Plum}\mathit{{}_1}} ,
 {\color{Black}\mathit{a}}
 {\color{Plum}\mathit{{}_2}} ,
 \ldots,
 {\color{Black}\mathit{a}}{}_ (
 {\color{black}\mathit{{}_n}}
 {\color{Blue}\mathit{{}_-}}
 {\color{Plum}\mathit{{}_1}} {}_)
 )

 {\color{Sepia}\mathit{for}}\;
 {\color{Black}\mathit{i}}\;
 {\color{Blue}\mathit{\gets}}\;
 {\color{Plum}\mathit{2}}\;
 {\color{Sepia}\mathit{to}}\;
 {\color{Black}\mathit{n}}\;
 {\color{Sepia}\mathit{do}}

 {\color{Sepia}\mathit{for}}\;
 {\color{Black}\mathit{j}}\;
 {\color{Blue}\mathit{\gets}}\;
 {\color{Plum}\mathit{0}}\;
 {\color{Sepia}\mathit{to}}\;
 {\color{Black}\mathit{n}}\;
 {\color{Blue}\mathit{-}}\;
 {\color{Black}\mathit{i}}\;
 {\color{Sepia}\mathit{do}}

 {\color{Sepia}\mathit{if}}\;
 {\color{Black}\mathit{a}}{}_ (
 {\color{Black}\mathit{{}_j}}{}_) \;
 {\color{Blue}\mathit{>}}\;
 {\color{Black}\mathit{a}}{}_ (
 {\color{Black}\mathit{{}_j}}
 {\color{Blue}\mathit{{}_+}}
 {\color{Plum}\mathit{{}_1}}{}_) \;
 {\color{Sepia}\mathit{then}}

 {\color{Black}\mathit{aux}}\;
 {\color{Blue}\mathit{\gets}}\;
 {\color{Black}\mathit{a}}{}_ (
 {\color{Black}\mathit{{}_j}}{}_) \;

 {\color{Black}\mathit{a}}{}_ (
 {\color{Black}\mathit{{}_j}}{}_) \;
 {\color{Blue}\mathit{\gets}}\;
 {\color{Black}\mathit{a}}{}_ (
 {\color{Black}\mathit{{}_j}}
 {\color{Blue}\mathit{{}_+}}
 {\color{Plum}\mathit{{}_1}}{}_)

 {\color{Black}\mathit{a}}{}_ (
 {\color{Black}\mathit{{}_j}}
 {\color{Blue}\mathit{{}_+}}
 {\color{Plum}\mathit{{}_1}}{}_) \;
 {\color{Blue}\mathit{\gets}}\;
 {\color{Black}\mathit{aux}}

 {\color{Sepia}\mathit{end \; if}}

 {\color{Sepia}\mathit{end \; for}}

 {\color{Sepia}\mathit{end \; for}}

 {\color{Sepia}\mathit{end \; procedure}}

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 dóna 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 ni, 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 al 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:


 a = \{55, 86, 48, 16, 82 \}\,

 \begin{array}{r}
 a_{4}= 82 \\
 a_{3}= 16 \\
 a_{2}= 48 \\
 a_{1}= 86 \\
 a_{0}= 55
 \end{array}

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


 n = 5 \,

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


 {\color{Sepia}\mathit{for}}\;
 {\color{Black}\mathit{i}}\;
 {\color{BlueViolet}\mathit{\gets}}\;
 {\color{Black}\mathit{2}}\;
 {\color{Sepia}\mathit{to}}\;
 {\color{Black}\mathit{n}}\;
 {\color{Sepia}\mathit{do}}

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 ni :


 {\color{Sepia}\mathit{for}}\;
 {\color{Black}\mathit{j}}\;
 {\color{BlueViolet}\mathit{\gets}}\;
 {\color{Black}\mathit{0}}\;
 {\color{Sepia}\mathit{to}}\;
 {\color{Black}\mathit{n-i}}\;
 {\color{Sepia}\mathit{do}}

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


 {\color{Sepia}\mathit{if}}\;
 {\color{Black}a_{(j)}}\;
 {\color{BlueViolet}>}\;
 {\color{Black}a_{(j+1)}}\;
 {\color{Sepia}\mathit{then}}

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


 \begin{array}{r||r|r|r|r|r}
 & J = 0 & j = 1 & j = 2 & j = 3 & \\
 \hline
 a_{4}& 82 & 82 & 82 & \to 82 & 86 \\
 a_{3}& 16 & 16 & \to 16 & \to 86 & 82 \\
 a_{2}& 48 & \to 48 & \to 86 & 16 & 16 \\
 a_{1}& \to 86 & \to 86 & 48 & 48 & 48 \\
 a_{0}& \to 55 & 55 & 55 & 55 & 55
 \end{array}

Per al cas de l'exemple, hem de:


 n = 5 \,

Per a la primera iteració del primer bucle:


 i = 2 \,

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


 {\color{Sepia}\mathit{for}}\;
 {\color{Black}\mathit{j}}\;
 {\color{BlueViolet}\mathit{\gets}}\;
 {\color{Black}\mathit{0}}\;
 {\color{Sepia}\mathit{to}}\;
 {\color{Black}\mathit{3}}\;
 {\color{Sepia}\mathit{do}}

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

Ara j val 1 i es comparen  a_1 \; a_2 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.


 \begin{array}{r||r|r|r|r}
 & J = 0 & j = 1 & j = 2 & \\
 \hline
 a_{4}& 86 & 86 & 86 & 86 \\
 a_{3}& 82 & 82 & \to 82 & 82 \\
 a_{2}& 16 & \to 16 & \to 55 & 55 \\
 a_{1}& \to 48 & \to 55 & 16 & 16 \\
 a_{0}& \to 55 & 48 & 48 & 48
 \end{array}

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

Primer j val 0, es comparen  a_0 \; a_1 , 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.


 \begin{array}{r||r|r|r}
 & J = 0 & j = 1 & \\
 \hline
 a_{4}& 86 & 86 & 86 \\
 a_{3}& 82 & 82 & 82 \\
 a_{2}& 55 & \to 55 & 55 \\
 a_{1}& \to 16 & \to 48 & 48 \\
 a_{0}& \to 48 & 16 & 16
 \end{array}

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

Quan j val 0, es comparen  a_0 \; a_1 é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  a_1 \; a_2 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  a_0 \; a_1 el 16 i el 48, que ja estan ordenats i es deixen igual.


 \begin{array}{r||r|r}
 & J = 0 & \\
 \hline
 a_{4}& 86 & 86 \\
 a_{3}& 82 & 82 \\
 a_{2}& 55 & 55 \\
 a_{1}& \to 48 & 48 \\
 a_{0}& \to 16 & 16
 \end{array}

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.


 {\color{Sepia}procedure}\;
 {\color{BlueViolet}BubbleSort2}\; (
 {\color{Black}a_{(0)}, a_{(1)}, a_{(2)}, \ldots, a_{(n-1)}})

 {\color{Black}i}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}1}\;

 {\color{Black}ordenat}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}no}\;

 {\color{Sepia}\mathit{while}}\;
 {\color{Black}\mathit{(i <n) \; \and \; (ordenat = no)}}\;
 {\color{Sepia}\mathit{do}}

 {\color{Black}i}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}i+1}\;

 {\color{Black}ordenat}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}if}\;

 {\color{Sepia}\mathit{for}}\;
 {\color{Black}\mathit{j}}\;
 {\color{BlueViolet}\mathit{\gets}}\;
 {\color{Black}\mathit{0}}\;
 {\color{Sepia}\mathit{to}}\;
 {\color{Black}\mathit{n-i}}\;
 {\color{Sepia}\mathit{do}}

 {\color{Sepia}\mathit{if}}\;
 {\color{Black}a_{(j)}}\;
 {\color{BlueViolet}>}\;
 {\color{Black}a_{(j+1)}}\;
 {\color{Sepia}\mathit{then}}

 {\color{Black}ordenat}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}no}\;

 {\color{Black}aux}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}a_{(j)}}\;

 {\color{Black}a_{(j)}}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}a_{(j+1)}}\;

 {\color{Black}a_{(j+1)}}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}aux}\;

 {\color{Sepia}\mathit{end \; if}}

 {\color{Sepia}\mathit{end \; for}}

 {\color{Sepia}\mathit{end \, while}}

 {\color{Sepia}\mathit{end \; procedure}}

 {\color{Sepia}procedure}\;
 {\color{BlueViolet}BubbleSort3}\; (
 {\color{Black}a_{(0)}, a_{(1)}, a_{(2)}, \ldots, a_{(n-1)}})

 {\color{Black}i}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}1}\;

 {\color{Sepia}\mathit{repetir}}

 {\color{Black}i}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}i+1}\;

 {\color{Black}ordenat}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}if}\;

 {\color{Sepia}\mathit{for}}\;
 {\color{Black}\mathit{j}}\;
 {\color{BlueViolet}\mathit{\gets}}\;
 {\color{Black}\mathit{0}}\;
 {\color{Sepia}\mathit{to}}\;
 {\color{Black}\mathit{n-i}}\;
 {\color{Sepia}\mathit{do}}

 {\color{Sepia}\mathit{if}}\;
 {\color{Black}a_{(j)}}\;
 {\color{BlueViolet}>}\;
 {\color{Black}a_{(j+1)}}\;
 {\color{Sepia}\mathit{then}}

 {\color{Black}ordenat}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}no}\;

 {\color{Black}aux}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}a_{(j)}}\;

 {\color{Black}a_{(j)}}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}a_{(j+1)}}\;

 {\color{Black}a_{(j+1)}}\;
 {\color{BlueViolet}\gets}\;
 {\color{Black}aux}\;

 {\color{Sepia}\mathit{end \; if}}

 {\color{Sepia}\mathit{end \; for}}

 {\color{Sepia}\mathit{until}}\;
 {\color{Black}\mathit{\neg (i <n) \; \or \; (ordenat = if)}}

 {\color{Sepia}\mathit{end \; procedure}}

Anàlisi[modifica | modifica el codi]

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

Rendiment de l'algorisme[modifica | modifica el codi]

Article principal: Cota ajustada asimptòtica

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


 c (n) =
 \cfrac{n^2-n}{2}

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


 \Theta (c (n)) =
 n^2 \;

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.


 \Theta (i (n)) =
 ? \;

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 | modifica el codi]

Article principal: Cota superior asimptòtica

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


 c (n) =
 \cfrac{n^2-n}{2}

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.


 i (n) =
 \cfrac{n^2-n}{2}

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


 O (c (n)) =
 O (i (n)) =
 n^2 \;

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 | modifica el codi]

Article principal: Cota inferior asimptòtica

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:


 \Omega (c (n)) =
 n^2 \;

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:


 i (n) =
 0 \;

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


 \Omega (i (n)) =
 1 \;

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 el algorisme més ineficient que existeix, encara que per a molts programadors sigui el més senzill d'implementar.

Conills i Tortugues (Jo-jos) (?)[modifica | modifica el codi]

La posició dels elements en l'ordenació de bombolla juguen un paper molt important en la determinació del rendiment. Els elements 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 | modifica el codi]

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 de 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 hacker, 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]

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

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

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Bubble-sort Modifica l'enllaç a Wikidata