Kupla lajittelu

Bubble sort on yksinkertainen lajittelualgoritmi. Se on helppo ymmärtää, joten sitä opetetaan yleensä uusille opiskelijoille. Se ei ole yhtä tehokas kuin jotkin muut lajittelualgoritmit.

Kuplalajittelun nimi tulee siitä, että jokainen listan kohde "kuplii" sinne, minne sen pitäisi mennä, kuten kuplat vedessä.

Kupla lajiteltu kuvattuna

Algoritmi

Algoritmi vertaa listan elementtipareja. Parin muodostavat elementit ovat vierekkäin. Aloitetaan listan toisesta päästä, ja kunkin parin kahta elementtiä verrataan toisiinsa järjestyksessä. Tämä tarkoittaa, että esimerkiksi ensimmäistä ja toista elementtiä verrataan, sitten toista ja kolmatta elementtiä, sitten kolmatta ja neljättä ja niin edelleen. Jos nykyisen parin elementit ovat eri järjestyksessä, elementit vaihtavat paikkaa. Tämä prosessi - kahden elementin vertailu - tehdään uudelleen ja uudelleen, kunnes koko lista on lajiteltu. Lista on lajiteltu, kun enää ei ole pareja, joita pitää vaihtaa.

Parhaassa tapauksessa, jossa lista oli jo lajiteltu ennen algoritmin suorittamista, algoritmin monimutkaisuus on O(n) (Big O -merkintä). Pahimmassa tapauksessa, jossa lista on aluksi lajiteltu päinvastoin, algoritmi on O(n²).

Esimerkki kuplalajittelusta. Vertaa seuraavaa paria luettelon alusta alkaen. Vaihda niiden paikat, jos ne eivät ole oikeassa järjestyksessä (parin toinen on pienempi kuin parin ensimmäinen). Jokaisen iteraation jälkeen on verrattava yhtä elementtiä vähemmän (viimeistä), kunnes vertailtavia elementtejä ei ole enää jäljellä.

Toteutus

Imperatiivisella ohjelmointikielellä kuplalajittelu voidaan toteuttaa käyttämällä lippumuuttujaa ja käymällä silmukalla läpi joukon elementit:

Aseta lippu lajiteltuna.
Aloitetaan yhdestä päästä ja tarkastellaan vektorin jokaista vierekkäistä elementtiparia peräkkäin (niiden järjestyksessä).
Jos parin elementit ovat epäjärjestyksessä, vaihda ne ja tyhjennä lajiteltu lippu.
Toista edelliset vaiheet, kunnes lajittelu pysyy asetettuna.

Vaihtoehtoisesti, koska suurin arvo nousee korkeimpaan indeksiin ensimmäisessä iteraatiossa ja on sitten saavuttanut lopullisen oikean sijaintinsa, myös kaksi toisiinsa sisäkkäin sijoitettua for-silmukkaa lajittelevat vektorin:

for top ≔ high(vektori)-1 downto low(vektori) do for current ≔ low(vektori) to top do if vector[current] > vector[current+1] then exchange(vector, current, current+1)

Aiheeseen liittyvät sivut

Insertion lajittelu
Valinnan lajittelu

Kysymyksiä ja vastauksia

K: Mikä on kuplalajittelu?

V: Bubble sort on yksinkertainen lajittelualgoritmi.

K: Miksi kuplalajittelu opetetaan yleensä uusille opiskelijoille?

V: Kuplalajittelu on helppo ymmärtää, joten sitä opetetaan yleensä uusille opiskelijoille.

K: Kuinka tehokas kuplalajittelu on verrattuna muihin lajittelualgoritmeihin?

V: Kuplalajittelu ei ole yhtä tehokas kuin jotkin muut lajittelualgoritmit.

K: Miksi kuplalajittelua kutsutaan kuplalajitteluksi?

V: Kuplalajittelun nimi tulee siitä, että jokainen listan kohde "kuplii" sinne, minne sen pitäisi mennä, kuten kuplat vedessä.

K: Soveltuuko kuplalajittelu suurille tietokokonaisuuksille?

V: Kuplalajittelu ei sovellu suurille tietokokonaisuuksille sen tehottomuuden vuoksi.

K: Mikä on kuplalajittelun prosessi?

V: Kuplalajittelussa verrataan vierekkäisiä elementtejä luettelossa ja vaihdetaan ne, jos ne ovat väärässä järjestyksessä.

K: Mitä voidaan sanoa kuplalajittelun monimutkaisuudesta?

V: Kuplalajittelun pahimman ja keskimääräisen tapauksen aikakompleksisuus on O(n^2), mikä tarkoittaa, että suurten tietokokonaisuuksien lajittelu voi kestää hyvin kauan.