Bubble-sort: diferència entre les revisions
Contingut suprimit Contingut afegit
m Correcció: fins > fins a |
m Correcció tipogràfica: espais sobrants |
||
Línia 504:
Tot i que l'ordenació de bombolla és un dels algorismes més senzills d'implementar, el seu ordre '' O (n <sup> 2 </sup>) '' 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 <sup> 2 </sup>) '', 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.
{{citar ref|cognoms = Astrachan|nom = Owen|any = 2003|títol = ordenació de bombolla: Un analistes arqueològic d'un algorisme|publicació = SIGCSE |url = http://www.cs.duke.edu/# onada/papers/bubble.pdf|fechaacceso = 9 març 2011|llengua = anglès}}</ref>
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".
L'ordenació de bombolla és [[Cota superior asimptòtica|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 [[Predictor de salts|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ó]].
== Vegeu també ==
| |||