Csakúgy, ahogy a buborékok felemelkednek egy pohár aljáról, a buborék rendezés is egy egyszerű algoritmus, amely rendezi a listát, lehetővé téve akár alacsonyabb, akár magasabb értékek felfelé buborékolását. Az algoritmus áthalad egy listán és összehasonlítja a szomszédos értékeket, felcserélve azokat, ha nem a megfelelő sorrendben vannak.
A legrosszabb esetben O (n ^ 2) komplexitása esetén a buborékok rendezése nagyon lassú más rendezési algoritmusokhoz, például a quicksorthoz képest. A fejlõdés az, hogy ez az egyik legkönnyebben válogatható algoritmus, amelyet a semmibõl megérteni és kódolni lehet.
Példa:
let arr = [4, 2, 6, 3, 9]; let sorted = false while(!sorted) { sorted = true for(var i = 0; i < arr.length; i++) { if(arr[i] < arr[i - 1]) { let temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; sorted = false; } } }Első lépés a listán:
- Kezdve
[4, 2, 6, 3, 9]az algoritmus összehasonlítja a tömb első két elemét, a 4-et és a 2-et. Felcseréli őket, mert 2 <4:[2, 4, 6, 3, 9] - Összehasonlítja a következő két értéket, a 4-et és a 6-ot. Mivel 4 <6, ezek már rendben vannak, és az algoritmus továbbhalad:
[2, 4, 6, 3, 9] - A következő két értéket is felcseréljük, mert 3 <6:
[2, 4, 3, 6, 9] - Az utolsó két érték, a 6 és a 9 már rendben van, ezért az algoritmus nem cseréli fel őket.
Második lépés a listán:
- 2 <4, tehát nincs szükség pozíciók cseréjére:
[2, 4, 3, 6, 9] - Az algoritmus felcseréli a következő két értéket, mert 3 <4:
[2, 3, 4, 6, 9] - Nincs csere, mint 4 <6:
[2, 3, 4, 6, 9] - Ismét 6 <9, tehát nem történik csere:
[2, 3, 4, 6, 9]
A lista már rendezve van, de a buborék rendezési algoritmus ezt nem veszi észre. Inkább teljes listát kell elvégeznie a listán, anélkül, hogy értékeket cserélne, hogy a lista rendezve legyen.
Harmadik lépés a listán:
[2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9]
Nyilvánvaló, hogy a buborékos rendezés messze nem a leghatékonyabb rendezési algoritmus. Ennek ellenére egyszerű körbefogni a fejét és megvalósítani önmagát.
Most pedig öntsön magának egy hideg, pezsgő italt - megérdemli.