Bubble Sort on yksinkertainen algoritmi, jota käytetään tietyn -elementit tarjotaan taulukon muodossa, jossa on n -elementtimäärä. Bubble Sort vertaa kaikkia elementtejä yksitellen ja lajittelee ne niiden arvojen perusteella.
Jos annettu taulukko on lajiteltava nousevassa järjestyksessä, kuplalajittelu alkaa vertaamalla taulukon ensimmäistä elementtiä toinen elementti, jos ensimmäinen elementti on suurempi kuin toinen, se vaihtaa molemmat elementit ja siirtyy sitten vertaamaan toista ja kolmatta elementtiä ja niin edelleen.
Jos meillä on yhteensä n elementtejä, meidän on toistettava tämä prosessi n-1 kertaa.
Se tunnetaan nimellä kupla lajittelu, koska jokaisella täydellisellä iteroinnilla tietyn matriisin suurin osa kuplii viimeistä sijaa tai korkeinta indeksiä kohti, aivan kuten vesikuplan noustessa veden pintaan.
Lajittelu tapahtuu siirtymällä läpi kaikki elementit yksitellen ja vertaamalla sitä viereiseen elementtiin ja vaihtamalla niitä tarvittaessa.
HUOMAUTUS: Jos et ole perehtynyt lajitteluun tietorakenteessa, sinun tulisi ensimmäinen oppii lajittelun perusteet.
Kuplalajittelualgoritmin toteuttaminen
Seuraavat ovat kuplalajittelun vaiheet (tietyn taulukon lajittelemiseksi nousevassa järjestyksessä):
- Aloita ensimmäisestä elementistä (indeksi = 0) ja vertaa nykyistä elementtiä taulukon seuraavaan elementtiin.
- Jos nykyinen elementti on suurempi kuin seuraava elementti taulukosta, vaihda ne.
- Jos nykyinen elementti on pienempi kuin seuraava elementti, siirry seuraavaan elementtiin. Toista vaihe 1.
Tarkastellaan taulukkoa, jonka arvot ovat {5, 1, 6, 2, 4, 3}
Alla on kuvallinen esitys siitä, kuinka kuplalajittelu lajittelee annetun taulukon.
Joten kuten yllä olevasta esityksestä voimme nähdä, ensimmäinen iteraatio 6 sijoitetaan viimeiseen hakemistoon, joka on sille oikea sijainti.
Vastaavasti toisen iteraation jälkeen 5 on toisessa viimeisessä hakemistossa ja niin edelleen.
Aika kirjoittaa koodi kuplalajittelulle:
Vaikka yllä oleva logiikka lajittelee lajittelemattoman taulukon, yllä oleva algoritmi ei silti ole tehokas, koska yllä olevan logiikan mukaisesti ulompi for -silmukka jatkaa 6 iteraation suorittamista, vaikka taulukko lajitellaan toisen iteraation jälkeen.
Voimme siis optimoida algoritmimme selvästi.
Optimoitu kuplalajittelualgoritmi
Kuplamme optimoimiseksi Lajittelualgoritmin avulla voimme ottaa käyttöön flag seuratakseen, vaihdetaanko elementtejä sisäisen for -silmukan sisään.
Siksi sisäisessä for -silmukassa tarkistamme, tapahtuuko elementtien vaihto aina.
Jos tietyn iteraation yhteydessä ei vaihdettu paikka tarkoittaa, että taulukko on lajiteltu ja voimme hypätä for -silmukasta kaikkien iteraatioiden suorittamisen sijaan.
Tarkastellaan matriisia arvoilla {11, 17, 18, 26, 23}
Alla on kuvaesitys siitä, kuinka optimoitu kuplalajittelu lajittelee annetun taulukon.
Kuten näemme, ensimmäisessä iteroinnissa tapahtui vaihtaminen, joten päivitimme flag -arvoksi 1, seurauksena suoritus siirtyy taas silmukkaan for. Mutta toisessa iteroinnissa ei tapahdu vaihtamista, joten flag -arvo pysyy 0 -kohdassa, ja suoritus hajoaa silmukasta.
Yllä olevassa koodissa funktiossa bubbleSort, jos yksi täydellinen jakso j iterointia (sisäinen for -silmukka), vaihtamista ei tapahdu, sitten flag pysyy 0 ja sitten irrotamme for -silmukoista, koska taulukko on jo lajiteltu.
Kuplalajittelun monimutkaisuusanalyysi
Kuplalajittelussa n-1 -vertailut tehdään ensimmäisellä kierroksella, n-2 2. passissa, n-3 3. passissa ja niin edelleen. Joten vertailujen kokonaismäärä on,
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2e.e O (n2)
Siksi Bubble Lajittelun aikakompleksisuus on O (n2).
Bubble Sortin tärkein etu on algoritmin yksinkertaisuus.
Bubble Sort -tilan tilan monimutkaisuus on O (1), koska muuttujalle temp tarvitaan vain yksi ylimääräinen muistitila.
Paras aika-monimutkaisuus on myös O (n), kun luettelo on jo lajiteltu.
Seuraavassa on Bubble Sort -algoritmin aika ja tila-monimutkaisuus.
Nyt kun olemme oppineet kuplalajittelualgoritmin, voit tarkistaa myös nämä lajittelualgoritmit ja niiden sovellukset:
- lisäyslajittelu
- valintalajittelu
- pikalajittelu
- yhdistä lajittelu
- kasan lajittelu
- laskulajittelu
