Kuplalajittelu

Käy listaa läpi yhä uudelleen ja vaihtaa keskenään vierekkäiset arvot, jotka ovat väärin päin. Jokaisen kierroksen jälkeen suurin jäljellä oleva arvo on lopussa.

paras Ω(n)
keskimääräinen Θ(n²)
huonoin O(n²)
tila O(1)
vakaa
ei tarvitse lisämuistia

Mitä nämä tarkoittavat?

Paras tapaus: miten aika kasvaa listan koon n mukana, kun syöte on tälle algoritmille helpoin.
Keskimääräinen: tavallinen kasvu n:n mukana. Kun kasvu on n², tuplasti arvoja vie noin nelinkertaisen ajan. n log n kasvaa paljon hitaammin.
Huonoin tapaus: kasvu vaikeimmalla syötteellä. Tärkeä silloin, kun nopeus ei saa koskaan romahtaa.
Tila: paljonko lisämuistia tarvitaan listan lisäksi. 1 tarkoittaa muutamaa muuttujaa, n listan kopiota.
Vakaa: kaksi yhtä suurta arvoa säilyttää alkuperäisen järjestyksensä. Tärkeää, kun tietueita lajitellaan yhden kentän mukaan.
Ei tarvitse lisämuistia: lajittelee itse listassa ilman toista listaa.

vertailu
siirto
lopullisella paikallaan

0 / 453 askelta

Vertailut Vaihdot

Paina Toista: viivat näyttävät, miten työmäärä kasvaa

Nopeus 8 askelta/s

Välilyönti: toisto tai tauko. Nuolinäppäimet: askel. Home ja End: alkuun tai loppuun.

Kokeile tätä: Valitse lähes järjestetty lista. Kun kierroksella ei tehdä yhtään vaihtoa, algoritmi lopettaa aikaisin.

Miten se toimii

Se vertaa kahta vierekkäistä arvoa kerrallaan ja vaihtaa ne, jos vasen on suurempi. Näin jokaisella kierroksella suurin arvo kulkee aivan oikeaan reunaan kuin nouseva kupla. Jos kierroksella ei tehdä yhtään vaihtoa, lista on jo järjestyksessä.

Milloin se on hyvä valinta

Oikeissa ohjelmissa tuskin koskaan, koska se on hidas pitkillä listoilla. Oppimiseen se sopii hyvin: siinä näkyy lajittelun perusajatus, vertailu ja vaihto. Nopea se on vain, kun lista on jo järjestyksessä.