Kuplalajittelu pidetään yhtenä yksinkertaisimmista lajittelualgoritmeista, joka toimii vaihtamalla toistuvasti vierekkäisiä elementtejä, jos ne ovat väärässä järjestyksessä. Kuplalajittelualgoritmin avulla näet, että suurin elementti (olettaen, että lajittelemme pienimmästä suurimpaan) ”kuplii” luettelon tai taulukon yläosaan.

Esimerkki:
Oletetaan, että haluamme lajitella luettelon tai joukon elementtejä nousevassa järjestyksessä (pienimmästä suurimpaan): List = (3,1,2)

Koska vaihtamista ei tapahtunut, tämä kertoo meille, että taulukko on lajiteltu jo nousevassa järjestyksessä!

Paras tapaus

Yritetään nyt samaa algoritmia uudelleen, mutta tällä kertaa parhaan mahdollisen skenaarion avulla, jolloin elementit on jo lajiteltu järjestyksessä ( nousevasti) haluaisimme.

Koska vaihtamista ei tapahtunut, olemme valmiita, ja algoritmi teki vain 2 vertailua ja matriisin elementtien lukumäärän kutsumme n = 3. Joten voimme nähdä, että n elementit, joissa tämä algoritmi parhaassa tapauksessa vie vain n-1-vertailut, n-1 = O (n)

Käytetty menettelytapa tai algoritmi on alla:

Tämä algoritmi käyttää lippua kertoa onko elementit vaihdettu vai ei , jonka avulla kuplalajittelualgoritmin paras tapa on olla O (n) O: n (n²) sijaan, kuten toinen lajittelu.

Yllä oleva algoritmi
Pahin tapaus = O (n²)
Paras tapaus = O (n)

Tarkastellaan kuplalajittelualgoritmin erilaista toteutusta:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

Yllä oleva algoritmi
Pahin tapaus = O (n²)
Paras tapaus = O (n²)

Pahin tapaus

Lajitellaan taulukko tai luettelo = (3,2,1) tämä olisi pahin tapaus, jossa luettelo on täysin päinvastaisessa järjestyksessä kuin mitä haluamme (nousevassa järjestyksessä) käyttämällä yllä olevaa algoritmia.

Ensimmäinen syöttö:
(3,2,1) – > Vertaa elementtejä 3 & 2
(2,3 , 1) – > Vaihda 3 & 2 vuodesta 2 < 3
(( 2,3,1) – > Vertaa elementtejä 3 & 1
(2,1,3) – > Vaihda 1 & 3 vuodesta 1 < 3

Second Pass:
(2,1,3) – > Vertaa elementtejä 2 & 1
(1,2,3) – > Vaihda 2 & 1 vuodesta 1 < 2
(1,2,3) – > Vertaa elementit 2 & 3
(1,2,3) – > Vaihtoa ei tarvita, koska 2 < 3

Olemme nyt lopettaneet silmukan molempien silmukoiden läpi, joten taulukko on lajiteltava nousevassa järjestyksessä.

Huomaa, että teimme 4 vertailua yllä olevassa toisessa esimerkissä, ja matriisin elementtien lukumäärä, jota kutsumme ’n’ = 3, joten tehtyjen vertailujen määrä on (n-1) ² ja (n-1) ² = O (n²)

Myös loistavaa kirjaa, joka valmistautuu koodaamiseen / ohjelmointihaastatteluihin, kutsutaan koodaavan haastattelun murtamiseksi. Se auttaa sinua tutustumaan lajittelualgoritmeihin ja ongelmanratkaisuun, joten muista tarkistaa se!

Kiitos tämän artikkelin lukemisesta, toivottavasti siitä on hyötyä kaikille! Jatka oppimista, ja jos haluat lisää algoritmianalyysivideoita, käy ja tilaa YouTube-kanavani (randerson112358 & compsci112358)

Katso seuraavat lisää sisältöä / videoita algoritmien analysoinnista ja ohjelmoinnista:

YouTube-kanava:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Verkkosivusto:

Video-oppaat toistumisen suhteen:

Video-opetus algoritmianalyysistä:

Twitter: