Kuplalajittelu (Bubble sort) — selitys, toimintaperiaate ja kompleksisuus

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ä.

Toimintaperiaate

Kuplalajittelu käy listin läpi toistuvasti ja vertailee vierekkäisiä alkioita. Jos pari on väärässä järjestyksessä, alkiot vaihdetaan keskenään. Tämä toimenpide "kuplii" suurimmat (tai pienimmät, riippuen järjestyssuunnasta) alkioista listan loppuun yhdellä läpikäynnillä. Prosessia toistetaan, kunnes koko lista on järjestyksessä.

Pseudokoodi (yksinkertainen versio)

 procedure bubbleSort(A : list of sortable items)     n := length(A)     for i from 0 to n-2 do         for j from 0 to n-2-i do             if A[j] > A[j+1] then                 swap A[j] and A[j+1]             end if         end for     end for end procedure

Optimoitu versio (aikasäästö)

Yksi yleinen optimointi on lisätä vaihdonseurantamuuttuja (esim. swapped). Jos yhdellä läpikäynnillä ei tehdä vaihtoja, lista on jo järjestyksessä ja voidaan lopettaa aikaisemmin. Lisäksi viimeisen vaihdon sijaintia voi seurata ja supistaa seuraavaa läpikäyntiä edelleen.

 procedure optimizedBubbleSort(A)     n := length(A)     repeat         swapped := false         for i from 0 to n-2 do             if A[i] > A[i+1] then                 swap A[i] and A[i+1]                 swapped := true             end if         end for         n := n - 1  // viimeinen alkio on nyt oikeassa paikassa     until not swapped end procedure

Esimerkki

Järjestetään lista [5, 3, 4, 1]

1. läpikäynti: [3, 4, 1, 5] (5 "kuplii" loppuun)
2. läpikäynti: [3, 1, 4, 5]
3. läpikäynti: [1, 3, 4, 5] (ei enää vaihtoja, lopetetaan)

Aikavaativuus ja tilavaativuus

Haitallisimmassa tapauksessa (worst-case): O(n²) — täytyy tehdä noin n(n−1)/2 vertailua ja vaihtoa.
Keskivertotapaus: O(n²).
Parhaimmillaan (best-case): O(n) — kun algoritmi on optimoitu tarkistamaan vaihdot ja lista on jo järjestyksessä.
Tilan tarve: O(1) — kuplalajittelu on in-place-algoritmi, joka tarvitsee vain muutaman apumuuttujan.

Ominaisuudet

Vakioiden stabiilisuus: Kuplalajittelu on stabiili, eli säilyttää samanarvoisten alkioiden alkuperäisen järjestyksen.
Helppo toteuttaa: Selkeä logiikka ja vähän koodia, siksi sopii opetukseen ja pieniin tehtäviin.
Huono skaalautuvuus: Suuressa datassa ja tuotantokäytössä tehokkaammat algoritmit (esim. quicksort, mergesort, heapsort) ovat yleensä parempia.

Milloin käyttää kuplalajittelua?

Pieniä listoihin tai tilanteisiin, joissa koodin selkeys ja opetus ovat tärkeämpiä kuin suorituskyky.
Kun data on lähes järjestyksessä — optimoitu kuplalajittelu voi olla silloin tehokas.
Kun tarvitaan vakaa ja in-place-lajittelu ilman lisämuistia.

Vertailu muihin algoritmeihin (lyhyt)

Quicksort ja mergesort tarjoavat yleensä paremmat käytännön ja teoreettiset suoritusajat suurille syötteille (O(n log n)).
Heapsort on in-place ja O(n log n) mutta ei stabiili ilman lisätä muutoksia.

Kuplalajittelu on hyvä oppimisväline ja toimiva pienissä tai melkein lajitelluissa aineistoissa, mutta sen O(n²)-kompleksisuus tekee siitä huonon valinnan suurille tietomäärille tuotantoympäristössä.

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.