Pikalajittelu

Valitsee yhden arvon, jakoalkion, ja siirtää pienemmät arvot sen vasemmalle ja suuremmat oikealle puolelle. Sitten sama tehdään kummallekin osalle.

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

0 / 187 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. Jakoalkio on aina jäljellä olevista pienin tai suurin, joten toinen osa jää tyhjäksi ja työ kasvaa kohti n²:ta.

Miten se toimii

Tässä jakoalkio on alueen viimeinen arvo. Arvot käydään läpi vasemmalta oikealle, ja jokainen arvo, joka ei ole jakoalkiota suurempi, vaihdetaan vasempaan osaan. Lopuksi jakoalkio siirretään osien väliin, jossa se pysyy lopullisesti. Kumpikin osa järjestetään samalla tavalla.

Milloin se on hyvä valinta

Käytännössä yksi nopeimmista lajittelutavoista, ja lisämuistia se tarvitsee tuskin lainkaan. Jos jakoalkio on kuitenkin toistuvasti huono, esimerkiksi jo järjestetyllä listalla, siitä tulee hidas. Siksi käytännössä jakoalkio valitaan huolellisemmin.