Bubble Sort selitetty

Aivan kuten tapa, jolla kuplat nousevat lasin pohjalta, kuplalajittelu on yksinkertainen algoritmi, joka lajittelee luettelon, jolloin joko alemmat tai suuremmat arvot voivat kuplia ylöspäin. Algoritmi kulkee luettelon läpi ja vertaa vierekkäisiä arvoja vaihtamalla niitä, jos ne eivät ole oikeassa järjestyksessä.

Pahimmassa tapauksessa O: n (n ^ 2) monimutkaisuudessa kuplalajittelu on hyvin hidasta verrattuna muihin lajittelualgoritmeihin, kuten pikalajitteluun. Ylöspäin on, että se on yksi helpoimmista lajittelualgoritmeista ymmärtää ja koodata tyhjästä.

Esimerkki:

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

Ensimmäinen luettelon läpi:

  • Aluksi [4, 2, 6, 3, 9]algoritmi vertaa taulukon kahta ensimmäistä elementtiä, 4 ja 2. Se vaihtaa ne, koska 2 <4:[2, 4, 6, 3, 9]
  • Se vertaa kahta seuraavaa arvoa, 4 ja 6. Koska 4 <6, nämä ovat jo kunnossa, ja algoritmi siirtyy eteenpäin: [2, 4, 6, 3, 9]
  • Kaksi seuraavaa arvoa vaihdetaan myös, koska 3 <6: [2, 4, 3, 6, 9]
  • Kaksi viimeistä arvoa, 6 ja 9, ovat jo järjestyksessä, joten algoritmi ei vaihda niitä.

Toinen luettelon läpikäynti:

  • 2 <4, joten sijainteja ei tarvitse vaihtaa: [2, 4, 3, 6, 9]
  • Algoritmi vaihtaa seuraavat kaksi arvoa, koska 3 <4: [2, 3, 4, 6, 9]
  • Ei vaihtoa kuin 4 <6: [2, 3, 4, 6, 9]
  • Jälleen 6 <9, joten vaihtoja ei tapahdu: [2, 3, 4, 6, 9]

Luettelo on jo lajiteltu, mutta kuplalajittelualgoritmi ei ymmärrä tätä. Sen on pikemminkin suoritettava koko läpikulku luettelon läpi vaihtamatta arvoja, jotta tiedetään, että luettelo on lajiteltu.

Kolmas luettelon läpikäynti:

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

Selvästi kuplalajittelu on kaukana tehokkaimmasta lajittelualgoritmista. Silti on helppo kietoa pääsi ympärille ja toteuttaa itse.

Mene nyt kaada itsellesi kylmä, kupliva juoma - ansaitset sen.