Kekolajittelu

Järjestää listan keoksi eli puuksi, jossa jokainen vanhempi on lapsiaan suurempi. Sitten se siirtää suurimman arvon loppuun yhä uudelleen.

paras Ω(n log n)
keskimääräinen Θ(n log n)
huonoin O(n log 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
lopullisella paikallaan

0 / 299 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. Keko syntyy lähes ilman vaihtoja, ja sitten jokainen kierros siirtää suurimman arvon loppuun.

Miten se toimii

Keko on tallessa itse listassa: paikan i arvon lapset ovat paikoissa 2i+1 ja 2i+2, ja suurin arvo on aina alussa. Se vaihdetaan loppuun, kekoa pienennetään yhdellä ja keko korjataan. Järjestetty osa kasvaa oikealta.

Milloin se on hyvä valinta

Kun nopeuden pitää pysyä hyvänä pahimmassakin tapauksessa eikä lisämuistia ole, esimerkiksi pienissä laitteissa. Keskimäärin se on pikalajittelua hitaampi, joten sitä käytetään usein varasuunnitelmana.