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