Valintalajittelu
Etsii pienimmän jäljellä olevan arvon ja vaihtaa sen seuraavalle paikalle. Vaihtoja on hyvin vähän, mutta vertailuja aina yhtä monta.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- ei
- kyllä
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
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.