Algoritmen for boblesortering krever et par nestede løkker. Den ytre sløyfen må gjentas en gang for hvert element i datasettet (av størrelse n) mens den indre sløyfen gjentas n ganger første gang den blir skrevet inn, n-1 ganger den andre, og så videre. Tenk på formålet med hver løkke. Som forklart ovenfor er boblesortering strukturert slik at det neste største elementet i dataene flyttes til hver sin plassering ved hver passering gjennom listen. Derfor, for å få alle n-elementene på de riktige stedene, må den ytre sløyfen utføres n ganger.
Den indre sløyfen utføres på hver iterasjon av den ytre sløyfen. Hensikten er å sette det nest største elementet som blir satt på plass. Den indre sløyfen sammenligner og bytter derfor tilstøtende elementer. For å bestemme kompleksiteten til denne sløyfen, beregner vi antall sammenligninger som må gjøres. På den første iterasjonen av den ytre sløyfen, mens du prøver å plassere det største elementet, må det være n – 1 sammenligninger: den første sammenligningen er gjort mellom det første og andre elementet, det andre er gjort mellom det andre og tredje elementet, og så videre til n-1. sammenligning er gjort mellom n-1 og n-elementet. På den andre iterasjonen av den ytre sløyfen er det ikke nødvendig å sammenligne det med det siste elementet i listen, fordi det ble satt på riktig sted i forrige pass. Derfor krever den andre iterasjonen bare n-2-sammenligninger. Dette mønsteret fortsetter til den nest siste iterasjonen av den ytre sløyfen når bare de to første elementene i listen er usortert; klart i dette tilfellet er bare en sammenligning nødvendig. Totalt antall sammenligninger er derfor (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 eller O (n2).
Det beste tilfellet for boblesortering oppstår når listen allerede er sortert eller nesten sortert. I tilfelle der listen allerede er sortert, vil boblesortering avsluttes etter den første iterasjonen, siden det ikke ble gjort noen bytter. Hver gang det blir gjort et pass gjennom listen og ingen bytter ble gjort, er det sikkert at listen er sortert. Boblesortering er også effektiv når ett tilfeldig element må sorteres i en sortert liste, forutsatt at nytt element plasseres i begynnelsen og ikke på slutten. Når den plasseres i begynnelsen, vil den ganske enkelt boble opp til riktig sted, og den andre iterasjonen gjennom listen vil generere 0 bytter og avslutte sorteringen. Husk at hvis det tilfeldige elementet er plassert på slutten, mister boblesorteringen sin effektivitet fordi hvert element som er større enn det må boble helt opp til toppen.
Det absolutt verste tilfellet for boblesortering er når det minste elementet på listen er i den store enden. Fordi i hver iterasjon bare det største usorterte elementet blir satt på sin rette plassering, når det minste elementet er på slutten, må det byttes hver gang gjennom listen, og det kommer ikke til fronten av listen til alle n iterasjoner har skjedd. I verste fall tar det n iterasjoner av n / 2 bytter, så ordren er igjen n2.
Beste sak: n Gjennomsnittlig sak: n2 Verste sak: n2