Valintalajittelu

Etsii pienimmän jäljellä olevan arvon ja vaihtaa sen seuraavalle paikalle. Vaihtoja on hyvin vähän, mutta vertailuja aina yhtä monta.

paras Ω(n²)
keskimääräinen Θ(n²)
huonoin O(n²)
tila O(1)
ei 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
pienin tähän asti
lopullisella paikallaan

0 / 399 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 käänteinen lista. Vertailuja tehdään täsmälleen yhtä monta kuin millä tahansa muulla listalla.

Miten se toimii

Järjestämättömästä osasta etsitään pienin arvo. Se vaihdetaan ensimmäisen järjestämättömän arvon kanssa, jolloin taas yksi arvo on lopullisella paikallaan. Kaikki jäljellä olevat arvot tarkistetaan aina, vaikka lista olisi jo järjestyksessä.

Milloin se on hyvä valinta

Hyödyllinen, kun datan siirtäminen on kallista mutta lukeminen halpaa, koska jokaiseen paikkaan tehdään enintään yksi vaihto. Muissa tapauksissa lisäyslajittelu on yleensä parempi valinta.