Objašnjeno razvrstavanje mjehurića

Baš kao i način na koji se mjehurići dižu s dna čaše, sortiranje mjehurića jednostavan je algoritam koji sortira popis, dopuštajući nižim ili višim vrijednostima da se oblače do vrha. Algoritam prelazi popis i uspoređuje susjedne vrijednosti, zamjenjujući ih ako nisu u ispravnom redoslijedu.

Uz najgori slučaj složenosti O (n ^ 2), mjehurićasto sortiranje vrlo je sporo u usporedbi s drugim algoritmima za sortiranje poput brzog sortiranja. Naopako je to što je to jedan od najlakših algoritama za sortiranje za razumijevanje i kodiranje od nule.

Primjer:

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

Prvo prođite kroz popis:

  • Polazeći od toga [4, 2, 6, 3, 9], algoritam uspoređuje prva dva elementa u nizu, 4 i 2. Zamijenjuje ih jer je 2 <4:[2, 4, 6, 3, 9]
  • Uspoređuje sljedeće dvije vrijednosti, 4 i 6. Kako je 4 <6, one su već u redu i algoritam se kreće dalje: [2, 4, 6, 3, 9]
  • Sljedeće dvije vrijednosti također se zamjenjuju jer je 3 <6: [2, 4, 3, 6, 9]
  • Posljednje dvije vrijednosti, 6 i 9, već su u redu, pa ih algoritam ne zamjenjuje.

Drugi prolazak kroz popis:

  • 2 <4, tako da nema potrebe za zamjenom pozicija: [2, 4, 3, 6, 9]
  • Algoritam zamjenjuje sljedeće dvije vrijednosti jer je 3 <4: [2, 3, 4, 6, 9]
  • Nema zamjene kao 4 <6: [2, 3, 4, 6, 9]
  • Opet, 6 <9, tako da ne dolazi do zamjene: [2, 3, 4, 6, 9]

Popis je već sortiran, ali algoritam sortiranja mjehurića to ne shvaća. Umjesto toga, treba dovršiti čitav prolazak kroz popis bez zamjene bilo kakvih vrijednosti kako bi znao da je popis sortiran.

Treće prolazak kroz popis:

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

Jasno je da je sortiranje mjehurića daleko od najučinkovitijeg algoritma za sortiranje. Ipak, jednostavno je zamotati glavu i implementirati se.

Sad si nalijte hladan, gaziran napitak - zaslužili ste.