Ordenament de bombeta

Representació animada d'ordenació d'un conjunt de números per mig de l'algoritme bombeta. Començant des de l'inici de l'apany, es compara cada parell d'elements adjacents. Si abdós no estan ordenats (el segon és menor que el primer), s'intercanvien les seues posicions. En cada iteración, un element menys necessita ser evaluats (l'últim), ya que no hi ha més elements a la seua dreta que necessiten ser comparats, ya que ya estan ordenats.

El ordenament de bombeta (Bubble Sort en anglés) és un senzill algoritme d'ordenament. Funciona revisant cada element de la llista que va a ser ordenada en el següent, intercanviant-los de posició si estan en l'orde equivocat. És necessari revisar vàries voltes tota la llista fins que no es necessiten més intercanvis, la qual cosa significa que la llista està ordenada. Este algoritme obté el seu nom de la forma en la que pugen per la llista els elements durant els intercanvis, com si anaren chicotetes «bombetes». També és conegut com el método de l'intercanvi directe. Ya que solament usa comparacions per a operar elements, li'l considera un algoritme de comparació, sent un dels més senzills d'implementar.

Descripció

Una manera simple d'expressar l'ordenament de bombeta en pseudocódigo és la següent:

$𝑝 𝑟 𝑜 𝑐 𝑒 𝑑 𝑖 𝑚 𝑖 𝑒 𝑛 𝑡 𝑜 𝐷 𝑒 𝐿 𝑎 𝐵 𝑢 𝑟 𝑏 𝑢 𝑗 𝑎 (𝑎_{0}, 𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{(}_{𝑛}_{-}_{1}_{)})$ $𝑝 𝑎 𝑟 𝑎 𝑖 \leftarrow 1 ℎ 𝑎 𝑠 𝑡 𝑎 𝑛 - 1 ℎ 𝑎 𝑐 𝑒 𝑟$ $𝑝 𝑎 𝑟 𝑎 𝑗 \leftarrow 0 ℎ 𝑎 𝑠 𝑡 𝑎 𝑛 - 𝑖 ℎ 𝑎 𝑐 𝑒 𝑟$ $𝑠 𝑖 𝑎_{(}_{𝑗}_{)} > 𝑎_{(}_{𝑗}_{+}_{1}_{)} 𝑒 𝑛 𝑡 𝑜 𝑛 𝑐 𝑒 𝑠$ $𝑎 𝑢 𝑥 \leftarrow 𝑎_{(}_{𝑗}_{)}$ $𝑎_{(}_{𝑗}_{)} \leftarrow 𝑎_{(}_{𝑗}_{+}_{1}_{)}$ $𝑎_{(}_{𝑗}_{+}_{1}_{)} \leftarrow 𝑎 𝑢 𝑥$ $𝑓 𝑖 𝑛 𝑠 𝑖$ $𝑓 𝑖 𝑛 𝑝 𝑎 𝑟 𝑎$ $𝑓 𝑖 𝑛 𝑝 𝑎 𝑟 𝑎$ $𝑓 𝑖 𝑛 𝑝 𝑟 𝑜 𝑐 𝑒 𝑑 𝑖 𝑚 𝑖 𝑒 𝑛 𝑡 𝑜$

Este algoritme realisa l'ordenament o reordenamiento d'una llista a de n valores, en este cas de n térmens numerats del 0 al n-1; consta de dos bucles anidados, un en l'índex i, que dona un tamany menor al recorregut de la bombeta en sentit invers de 2 a n, i un segon bucle en l'índex j, en un recorregut des de 0 fins a n-i, per a cada iteración del primer bucle, que indica el lloc de la bombeta.

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

Esta comparació es repetix en el centre dels dos bucles, donant lloc a una llista ordenada. Pot vore's que el número de repeticions solament depén de n i no de l'orde dels térmens, açò és, si passem a l'algoritme una llista ya ordenada, realisarà totes les comparacions exactament igual que per a una llista no ordenada. Esta és una característica d'este algoritme. Després vorem una variant que evita este inconvenient.

Per a comprendre el funcionament, vejam un eixemple senzill:

Tenim una llista de números que cal ordenar:

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

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

Podem vore que la llista que té cinc térmens, després:

n = 5

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

𝑝 𝑎 𝑟 𝑎 𝑖 \leftarrow 2 ℎ 𝑎 𝑠 𝑡 𝑎 𝑛 ℎ 𝑎 𝑐 𝑒 𝑟

que en este cas serà de 2 a 5. Per a cada u dels valors de i, j prendrà successivament els valors de 0 fins a n-i:

𝑝 𝑎 𝑟 𝑎 𝑗 \leftarrow 0 ℎ 𝑎 𝑠 𝑡 𝑎 𝑛 - 𝑖 ℎ 𝑎 𝑐 𝑒 𝑟

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

𝑠 𝑖 a_{(j)} > a_{(j + 1)} 𝑒 𝑛 𝑡 𝑜 𝑛 𝑐 𝑒 𝑠

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

\begin{matrix} j = 0 & j = 1 & j = 2 & j = 3 \\ 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{matrix}

Per al cas de l'eixemple, tenim que:

n = 5

Per a la primera iteración del primer bucle:

i = 2

i j prendrà els valors de 0 fins a 3:

𝑝 𝑎 𝑟 𝑎 𝑗 \leftarrow 0 ℎ 𝑎 𝑠 𝑡 𝑎 3 ℎ 𝑎 𝑐 𝑒 𝑟

Quan j val 0, es comparen $a_{0} a_{1}$ , el 55 i el 86, ya que 55 < 86, no es permuta l'orde.

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 repetix el procés fins que j valga 3, donant lloc a una llista parcialment ordenada. Podem vore que el terme de major valor està en el lloc més alt.

\begin{matrix} j = 0 & j = 1 & j = 2 \\ 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{matrix}

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 a j = 1 es compara el 55 en el 16 i es canvien d'orde.

Per a j = 2 es compara el 55 i el 82 i es deixen com estan, finalisant el bucle en una llista millor ordenada. Pot vore's que els dos valors més alts ya ocupen el seu lloc. No s'ha realisat cap comparació en el terme quart, ya que ya se sap que despuix del primer cicle és el major de la llista.

L'algoritme consistix en comparacions successives de dos térmens consecutius ascendint d'avall dalt en cada iteración, com l'ascensió de les bombetes d'aire en l'aigua, d'ahí el nom del procediment. En la primera iteración el recorregut ha segut complet, en el segon s'ha deixat l'últim terme, en tindre ya el major dels valors; en els successius s'anirà deixant de realisar les últimes comparacions, com es pot vore.

\begin{matrix} j = 0 & j = 1 \\ 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{matrix}

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

Quan j val 0, es comparen $a_{0} a_{1}$ , açò és, el 48 i el 16. Ya que 48 és major que 16 es permuten els valors, donant lloc a una llista alguna cosa més ordenada que l'anterior. Des d'esta nova ordenació, j passa a valdre 1, en lo que es comparen els térmens $a_{1} a_{2}$ el 48 i el 55 que queden en el mateix orde.

En este cas la bombeta ha ascendit menys que en els casos anteriors, i la llista està ya ordenada, pero l'algoritme tindrà que completar-se, realisant una última iteración.

Cal tindre en conte que el bucle realisa un número fix de repeticions i per a finalisar tindran que completar-se, encara en el cas extrem, de que la llista estiguera prèviament ordenada.

Per últim i val 5 i j solament pot val 0, en lo que només es realisarà una comparació de $a_{0} a_{1}$ el 16 i el 48, que ya estan ordenats i es deixen igual.

\begin{matrix} j = 0 \\ a_{4} & 86 & 86 \\ a_{3} & 82 & 82 \\ a_{2} & 55 & 55 \\ a_{1} & \to 48 & 48 \\ a_{0} & \to 16 & 16 \end{matrix}

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

Una variant que finalisa en cas que la llista estiga ordenada, pot ser la següent: com en l'eixemple anterior, amprant un centinela ordenat, que detecta que no s'ha modificat la llista en un recorregut de la bombeta, i que per tant la llista ya està ordenada, finalisant immediatament.

$p r o c e d i m i e n t o D e L a B u r b u j a 2 (a_{(0)}, a_{(1)}, a_{(2)}, \dots, a_{(n - 1)})$ $i \leftarrow 1$ $o r d e n a d o \leftarrow n o$ $𝑚 𝑖 𝑒 𝑛 𝑡 𝑟 𝑎 𝑠 (𝑖 < 𝑛) \land (𝑜 𝑟 𝑑 𝑒 𝑛 𝑎 𝑑 𝑜 = 𝑛 𝑜) ℎ 𝑎 𝑐 𝑒 𝑟$ $i \leftarrow i + 1$ $o r d e n a d o \leftarrow s i$ $𝑝 𝑎 𝑟 𝑎 𝑗 \leftarrow 0 ℎ 𝑎 𝑠 𝑡 𝑎 𝑛 - 𝑖 ℎ 𝑎 𝑐 𝑒 𝑟$ $𝑠 𝑖 a_{(j)} > a_{(j + 1)} 𝑒 𝑛 𝑡 𝑜 𝑛 𝑐 𝑒 𝑠$ $o r d e n a d o \leftarrow n o$ $a u x \leftarrow a_{(j)}$ $a_{(j)} \leftarrow a_{(j + 1)}$ $a_{(j + 1)} \leftarrow a u x$ $𝑓 𝑖 𝑛 𝑠 𝑖$ $𝑓 𝑖 𝑛 𝑝 𝑎 𝑟 𝑎$ $𝑓 𝑖 𝑛 𝑚 𝑖 𝑒 𝑛 𝑡 𝑟 𝑎 𝑠$ $𝑓 𝑖 𝑛 𝑝 𝑟 𝑜 𝑐 𝑒 𝑑 𝑖 𝑚 𝑖 𝑒 𝑛 𝑡 𝑜$

$p r o c e d i m i e n t o D e L a B u r b u j a 3 (a_{(0)}, a_{(1)}, a_{(2)}, \dots, a_{(n - 1)})$ $i \leftarrow 1$ $𝑟 𝑒 𝑝 𝑒 𝑡 𝑖 𝑟$ $i \leftarrow i + 1$ $o r d e n a d o \leftarrow s i$ $𝑝 𝑎 𝑟 𝑎 𝑗 \leftarrow 0 ℎ 𝑎 𝑠 𝑡 𝑎 𝑛 - 𝑖 - 1 ℎ 𝑎 𝑐 𝑒 𝑟$ $𝑠 𝑖 a_{(j)} > a_{(j + 1)} 𝑒 𝑛 𝑡 𝑜 𝑛 𝑐 𝑒 𝑠$ $o r d e n a d o \leftarrow n o$ $a u x \leftarrow a_{(j)}$ $a_{(j)} \leftarrow a_{(j + 1)}$ $a_{(j + 1)} \leftarrow a u x$ $𝑓 𝑖 𝑛 𝑠 𝑖$ $𝑓 𝑖 𝑛 𝑝 𝑎 𝑟 𝑎$ $ℎ 𝑎 𝑠 𝑡 𝑎 𝑞 𝑢 𝑒 \neg (𝑖 < 𝑛) \lor (𝑜 𝑟 𝑑 𝑒 𝑛 𝑎 𝑑 𝑜 = 𝑠 𝑖)$ $𝑓 𝑖 𝑛 𝑝 𝑟 𝑜 𝑐 𝑒 𝑑 𝑖 𝑚 𝑖 𝑒 𝑛 𝑡 𝑜$

Anàlisis

Eixemple de l'ordenament de bombeta ordenant una llista de números aleatoris.

Rendiment de l'algoritme

AP

A l'algoritme de la bombeta, per a ordenar un apany de n térmens, té que realisar sempre el mateix número de comparacions:

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

Açò és, el número de comparacions c(n) no depén de l'orde dels térmens, si no del número de térmens:

Θ (c (n)) = n^{2}

Per lo tant la cota ajustada asintòtica del número de comparacions pertany a l'orde de n quadrat.

El número d'intercanvis i(n), que cal realisar depén de l'orde dels térmens i podem diferenciar, el cas millor, si l'apany està prèviament ordenat, i el cas pijor, si l'apany està ordenat en orde invers:

Θ (i (n)) = ?

Per lo que no es pot determinar una cota ajustada asintòtica del número d'intercanvis, ya que este dependrà de l'orde de l'apany en qüestió.

Rendiment en el cas desfavorable

AP Si passem a l'algoritme un apany ordenat en orde invers realisarà un número de comparacions:

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

Com ya hem dit anteriorment, i tindrà que realisar un número igual d'intercanvis entre els térmens de l'apany, ya que en cada comparació els térmens estaran desordenats, i es realisarà l'intercanvi.

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

Per lo tant en el cas més desfavorable tant el número de comparacions com el d'intercanvis coincidixen:

O (c (n)) = O (i (n)) = n^{2}

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

Rendiment en casos òptims

AP

En el cas òptim, el més favorable, és l'ordenació d'un apany ya ordenat. En este cas el número de comparacions serà el mateix que en qualsevol atre cas:

Ω (c (n)) = n^{2}

La cota inferior asintòtica del número de comparacions pertany a l'orde de n quadrat, com en els demés casos, pero en totes les comparacions l'orde és el correcte i per tant no es realisa cap intercanvi:

i (n) = 0

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

Ω (i (n)) = 1

L'ordenament de bombeta té una complexitat Ω(n²) igual que ordenament per selecció. Quan una llista ya està ordenada, a diferència del ordenament per inserció que passarà per la llista una volta i trobarà que no hi ha necessitat d'intercanviar les posicions dels elements, el método d'ordenació per bombeta està forçat a passar per dites comparacions, lo que fa que la seua complexitat siga quadràtica en el millor dels casos. Açò ho cataloga com un dels algoritmes d'ordenació més ineficientes que existixen, encara que para molts programadors siga el més senzill d'implementar.

Referències

Vore també

Algoritme d'ordenament

Este artícul conté una traducció derivada de «Ordenamiento de burbuja» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.