Bubble Sort magyarázat

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.