Lisäyslajittelu
Rakentaa vasemmalle järjestetyn osan arvo kerrallaan. Jokainen uusi arvo nostetaan pois ja siirretään vasemmalle, kunnes vastaan tulee pienempi arvo.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- kyllä
- 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
- kädessä
- järjestetty osa
- lopullisella paikallaan
Väärässä järjestyksessä olevat parit: 154 (alussa: 154) väärässä järjestyksessä järjestetty Molemmat akselit: arvot pienimmästä suurimpaan
Paina Toista: viivat näyttävät, miten työmäärä kasvaa
Paina Toista tai käy algoritmi läpi askel kerrallaan.
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. Juuri mitään ei tarvitse siirtää, joten se valmistuu hyvin harvoilla askelilla.
Miten se toimii
Vasen osa on aina järjestyksessä. Seuraava arvo nostetaan pois, jokainen sitä suurempi arvo järjestetyssä osassa siirretään yhden paikan oikealle, ja arvo pudotetaan syntyneeseen aukkoon. Näin moni järjestää pelikortit kädessään.
Milloin se on hyvä valinta
Hyvä valinta lyhyille ja lähes järjestetyille listoille, joilla se on hyvin nopea. Lajittelukirjastot käyttävät sitä listan pieniin paloihin nopeampien menetelmien sisällä.