Taula de continguts:
Definició: què significa Bubble Sort?
L’ordenament de les bombolles és un algorisme d’ordenació que funciona trepitjant repetidament llistes que s’han d’ordenar, comparant cada parell d’elements adjacents i canviant-los si no estan en un ordre incorrecte. Aquest procediment de pas es repeteix fins que no es requereixin swaps, cosa que indica que la llista està ordenada. La classificació de bombolles rep el seu nom perquè els elements més petits apareixen cap a la part superior de la llista.
El tipus de bombolla també es denomina tipus de comparació o tipus de comparació.
Techopedia explica Sort de bombolles
L’ordenació de bombolles té el pitjor dels casos i la complexitat mitjana d’O (n2), on n és el nombre d’elements ordenats. A diferència dels altres algorismes d’ordenació, l’ordenació de bombolles detecta si la llista ordenada s’incorpora de manera eficient a l’algorisme. El rendiment d’ordenació de bombolles sobre una llista ja ordenada és O (n).
La posició dels elements en el tipus de bombolles té un paper important en la determinació del rendiment. Al principi, els grans elements no representen cap problema, ja que es poden canviar fàcilment. Els petits elements cap al final passen lentament al començament. Com a tal, aquests elements s’anomenen conills i tortugues.
L’algoritme d’ordenació de bombolles es pot optimitzar posant elements més grans a la posició final. Després de cada passada, tots els elements posteriors a l’últim intercanvi s’ordenen i no cal tornar a revisar-los, per això es pot ometre el seguiment de les variables intercanviades.
