Pikalajittelu
Valitsee yhden arvon, jakoalkion, ja siirtää pienemmät arvot sen vasemmalle ja suuremmat oikealle puolelle. Sitten sama tehdään kummallekin osalle.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- 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
- jakoalkio
- lopullisella paikallaan
Rekursiosyvyys: 0 · pienin mahdollinen: 4 · pahin: 23 odottaa jakoalkiotaan
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 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.