Quicksort on suosittu lajittelualgoritmi, joka tunnetaan vaikuttavasta O(n log n):n aikamonimutkaisuudestaan ja "Divide and Conquer" -strategiastaan. Se toimii pohjimmiltaan valitsemalla "pivot"-elementti taulukosta ja jakamalla muut elementit kahteen luokkaan - pivotia pienempiin ja sitä suurempiin. Tämä prosessi sijoittaa nivelen onnistuneesti todelliseen paikkaansa lajiteltuun taulukkoon.
Kun se on kehitetty puhtaasti toiminnallisella kielellä, kuten Haskell, sen toteutus voi olla ytimekäs ja tyylikäs säilyttäen samalla korkean suorituskyvyn. Haskellin ainutlaatuisen lähestymistavan toiminnalliseen ohjelmointiin ansiosta Quicksort voidaan toteuttaa vain muutamalla rivillä.
Ratkaisu Quicksortin avulla
Pikalajittelualgoritmin tarjoama ratkaisu on erityisen hyvä tietosarjoille, jotka seuraavat "satunnaistettua" järjestystä eivätkä ole voimakkaasti vinossa. Quicksortin tehokkuus ja tyylikkyys piilee toimintojen järjestyksessä – alkaen pivotin valinnasta ja sitä seuranneesta osioituksesta.
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (pivot:rest) = quicksort lesser ++ [pivot] ++ quicksort greater
where
lesser = filter (< pivot) rest
greater = filter (>= pivot) rest
Vaiheittainen selitys
Koodi alkaa tyyppiilmoituksella, pikalajittelu :: Järjestys a => [a] -> [a]. Tämä osoittaa, että pikalajittelutoiminto ottaa listan järjestettävistä elementeistä ja palauttaa toisen luettelon samantyyppisistä elementeistä.
Itse koodi alkaa peruskirjaimella, pikalajittelu [] = []. Tämä yksinkertaisesti sanoo, että tyhjän luettelon lajiteltu versio on toinen tyhjä luettelo.
Pikalajittelutoiminnon keskeinen osa on rekursiovaihe. Tässä vaiheessa hyödynnetään Haskellin kuvioiden yhteensopivuuden kauneutta. Tapaus pikalajittelu (pivot:rest) ottaa listan pivotin (pää) ja lopun (häntä) ja juuri tämä vaihe jakaa luettelon kahteen osaan.
Tämän jälkeen funktio suodattaa kaikki pivotia pienemmät elementit listaksi nimen perusteella vähemmän, ja kaikki elementit, jotka ovat suurempia tai yhtä suuria kuin pivot toiseen nimettyyn luetteloon suurempi.
Lopussa se lajittelee rekursiivisesti pienemmät ja suuremmat luettelot ja yhdistää nämä kaksi pivotilla keskellä.
Haskellin toiminnallinen olemus
Quicksort kuvaa erinomaisesti Haskellin toiminnallisen ohjelmoinnin tehoa ja kauneutta. Toiminnot, kuten suodatin, joka ottaa predikaatin ja listan ja palauttaa listan elementeistä, jotka täyttävät predikaatin, tekevät pikalajittelualgoritmista yksinkertaisen ja selkeän.
Myös Haskellin rekursioluonne, joka näkyy pikalajittelun määritelmässä pienemmille ja suuremmille, toteuttaa sujuvasti "Divide and Conquer" -konseptin, johon pikalajittelu perustuu.
Haskell-kirjastot ja korkeamman asteen funktiot auttaa suuresti tekemään koodista ytimekäs ja ilmeikäs. Luontainen staattinen kirjoittaminen auttaa luomaan turvallisempaa ja ennustettavampaa koodia.
Yhdistä eleganssi ja tehokkuus
Yhteenvetona voidaan todeta, että pikalajittelu Haskellissa on erinomainen esimerkki siitä, kuinka toimiva ohjelmointi voi yhdistää eleganssin ja tehokkuuden. Yksinkertaisuudestaan huolimatta se on tehokas lajittelualgoritmi, joka sopii monenlaisiin tehtäviin.
On kuitenkin syytä huomata, että vaikka pikalajittelu on yleensä nopeaa, sen suorituskyky voi olla haavoittuva tietyissä tietojoukoissa (esim. kun syöttöluettelo on jo lajiteltu). Siksi ota aina huomioon tehtäväsi erityisvaatimukset ja konteksti, kun päätät, mitä lajittelualgoritmia käytät.
