Lomituslajittelu
Jakaa listan kahtia, järjestää kummankin puolikkaan ja lomittaa ne yhdeksi järjestetyksi listaksi.
- paras Ω(n log n)
- keskimääräinen Θ(n log n)
- huonoin O(n log n)
- tila O(n)
- vakaa
- tarvitsee 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
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 lista, jossa on vähän eri arvoja. Kahdesta yhtä suuresta arvosta otetaan ensin vasemman puolikkaan arvo, joten järjestys säilyy.
Miten se toimii
Listaa jaetaan, kunnes jokaisessa palassa on vain yksi arvo. Sellainen pala on jo järjestyksessä. Sitten palat lomitetaan pareittain: kummankin palan ensimmäisiä arvoja verrataan ja pienempi otetaan, yhä uudelleen. Animaation nostettu rivi on lomituksen tarvitsema lisätila.
Milloin se on hyvä valinta
Kun nopeuden pitää pysyä hyvänä pahimmassakin tapauksessa ja yhtä suurten arvojen pitää säilyttää järjestyksensä. Sekä Python että Java käyttävät lomituslajittelun muunnelmaa. Haittapuoli on sen tarvitsema lisämuisti.