A buborékrendezés az egyik legegyszerűbb rendezés. Az alapötlete az, hogy a maximális elemet cserékkel „felbuborékoltatjuk” a tömb végére. A buborékoltatás úgy működik, hogy párosával haladunk végig az elemeken és a rosszul álló szomszédos elempárokat felcseréljük. Így a legnagyobb elem eljut a tömb végére. Ezt kell ismételgetni, míg egy rendezett tömböt nem kapunk.

A buborékrendezés stabil, azaz az azonos kulcsú elemek egymáshoz viszonyított sorrendjét megőrzi. Például, ha van kettő 32-es, akkor azok ugyanabban a sorrendben lesznek a rendezés után, mint ahogyan rendezés előtt voltak. Ez azért van, mert az egyenlő szomszédokat nem cseréli meg.

A rendezendő számokat kulcsoknak is szokás nevezni. A bemenő kulcsokat helyben rendezi, tehát a számokat az $A$ tömbön belül rakja a helyes sorrendbe és legfeljebb csak állandó számú elem tárolódik a tömbön kívül.

Az algoritmus az összehasonlító rendezések közé tartozik, azaz az elemek sorrendjét azok összehasonlításával állapítja meg.

Működése:

A bemenet számok $n$ elemű $(a_1, a_2, ..., a_n)$ sorozata, a kimenet pedig az $a_1, a_2, ..., a_n$ számok egy olyan $(a_1', a_2', ..., a_n')$ átrendezése, ahol $a_1' \leq a_2' \leq ... \leq a_n'$.

Az algoritmus egy külső és egy belső ciklusból áll. A külső ciklus mutatja azt, hogy hányadik elemig rendezetlen még a tömb. Kezdetben mindegyik elemet rendezetlennek vesszük, majd „buborékoltatásonként” eggyel rövidebb lesz a rendezetlen rész. A belső ciklus az aktuálisan vizsgált pár összehasonlításáról gondoskodik.

A cserék száma megegyezik a tömb elemei között fennálló inverziók számával. (Inverzió: a nagyobb értékű elem megelőzi a kisebb értékűt). Minden csere pontosan egy inverziót szüntet meg a két szomszédos elem között, újat viszont nem hoz létre. A rendezett tömbben nincs inverzió, egyetlen cserét sem kell végrehajtani.

Műveletigény:

Egy csere valójában 3 mozgatást jelent, így a buborékrendezés szükségtelenül sok mozgatást hajt végre, ezért nagyméretű adatoknál általában nem a legjobb választás. Az összehasonlítások száma bemenettől függetlenül ugyanannyi lesz egy adott számú bemenet esetén. Viszont a cserék száma változhat a bemenettől függően. A műveletigényet a cserék ($Cs$) és az összehasonlítások ($Ö$) számával fogjuk kiszámítani:

• $Ö(n) = (n-1) + (n-2) + ... + 1 =$
  $\frac{n \cdot (n-1)}{2} = \frac{n^2-n}{2} \in \Theta (n^2)$

• $mCs(n) = 0$, amikor monoton növekvően rendezett a tömb
• $MCs(n) = Ö(n)$, amikor minden összehasonlítást csere követ, azaz fordítottan rendezett a tömb
• $ACs(n) = \frac{n \cdot (n-1)}{4} = \Theta (n^2)$, részletes kiszámítása itt található: Hagyomanyos_rendezesek.pdf

• $MT(n) \in \Theta(n^2)$
• $AT(n) \in \Theta(n^2)$
• $mT(n) \in \Theta(n)$

Gyakorlati alkalmazása:

Az egyik legkönnyebben implementálható rendező algoritmus, ezért ha valakinek kevés elemet kell rendeznie és nem számít a hatékonyság, általában ezt fogja használni.