La fel ca felul în care bulele se ridică din fundul unui pahar, sortare cu bule este un algoritm simplu care sortează o listă, permițând fie valori mai mici, fie mai mari să meargă în sus. Algoritmul parcurge o listă și compară valorile adiacente, schimbându-le dacă acestea nu sunt în ordinea corectă.

Cu o complexitate în cel mai rău caz de O (n ^ 2), sortarea cu bule este foarte lentă în comparație cu alți algoritmi de sortare precum quicksort. Dezavantajul este că este unul dintre cei mai ușori algoritmi de sortare de înțeles și codat de la zero.

Exemplu:

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;
    }
  }
}

Prima trecere prin listă:

  • Incepand cu [4, 2, 6, 3, 9], algoritmul compară primele două elemente din matrice, 4 și 2. Le schimbă deoarece 2 <4: [2, 4, 6, 3, 9]
  • Compară următoarele două valori, 4 și 6. Deoarece 4 <6, acestea sunt deja în ordine, iar algoritmul continuă: [2, 4, 6, 3, 9]
  • Următoarele două valori sunt, de asemenea, schimbate, deoarece 3 <6: [2, 4, 3, 6, 9]
  • Ultimele două valori, 6 și 9, sunt deja în ordine, deci algoritmul nu le schimbă.

A doua trecere prin listă:

  • 2 <4, deci nu este nevoie să schimbați pozițiile: [2, 4, 3, 6, 9]
  • Algoritmul schimbă următoarele două valori, deoarece 3 <4: [2, 3, 4, 6, 9]
  • Fără swap ca 4 <6: [2, 3, 4, 6, 9]
  • Din nou, 6 <9, deci nu are loc niciun swap: [2, 3, 4, 6, 9]

Lista este deja sortată, dar algoritmul de sortare cu bule nu realizează acest lucru. Mai degrabă, trebuie să finalizeze o întreagă trecere prin listă fără a schimba valori pentru a ști că lista este sortată.

A treia trecere prin listă:

  • [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]

În mod clar sortarea cu bule este departe de cel mai eficient algoritm de sortare. Totuși, este simplu să vă înfășurați capul și să vă implementați.

Acum du-te și toarnă-ți o băutură rece, cu bule – o merite.