Quicksort on yksi tehokkaimmista lajittelualgoritmeista, jonka keskimääräinen aikamonimutkaisuus on O(n log n). Jaa ja hallitse -metodologiaan perustuen se osoittaa vaikuttavaa suorituskykyä suurten tietojoukkojen lajittelussa. Brittiläisen tietojenkäsittelytieteilijän Tony Hoaren vuonna 1959 keksimä ja vuonna 1961 julkaistu Quicksortista on tullut olennainen osa tietojenkäsittelytieteitä ja ohjelmointia..
Quicksort's suosio johtuu myös sen helppoudesta toteuttaa useilla ohjelmointikielillä. Tässä artikkelissa perehdymme siihen, kuinka Quicksort voidaan toteuttaa käyttämällä Haskell-ohjelmointikieltä, staattisesti kirjoitettua toiminnallista ohjelmointikieltä, joka tunnetaan puhtaudesta, ytimekkyydestään ja tyylikkyydestään.
Kuinka Quicksort toimii?
Quicksort toimii valitsemalla "pivotin" tietojoukosta ja jakamalla muut elementit kahteen ryhmään – pivotia pienemmät ja pivotia suuremmat elementit. Tämä vaihe, joka tunnetaan nimellä "osiointi", suoritetaan rekursiivisesti, kunnes luettelo on lajiteltu.
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
Yllä oleva Haskell-koodi alkaa määrittelemällä tyhjälle listalle perustapaus, joka palauttaa tyhjän luettelon. Ei-tyhjälle luettelolle se valitsee pivotin (tässä tapauksessa luettelon ensimmäisen elementin) ja suodattaa sitten loput luettelosta kahdeksi alaluetteloksi – toisessa, jonka elementit ovat pienempiä kuin pivot, ja toisessa, joiden elementit ovat suurempia kuin tai yhtä suuri kuin nivel.
Haskell-toteutuksen ymmärtäminen
Haskell-toteutuksessamme hyödynnämme kielen tehokasta luettelon ymmärtämistä ja korkeamman asteen toimintoja.
Koodirivi "(pikalajittelu pienempi) ++ [p] ++ (pikalajittelu suurempi)" kuvaa ytimekkäästi pikalajittelun olemuksen – se lajittelee rekursiivisesti sekä "pienen" että "suuremman" aliluettelot ja ketjuttaa sitten nämä lajitellut alaluettelot pivotiin. keskellä. Tämä on hajota ja hallitse -strategia toiminnassa.
Yksinkertaisuudestaan huolimatta tämä toteutus voi olla tehoton suurille luetteloille, koska se suodattaa jokaisen aliluettelon kahdesti. Siitä huolimatta se toimii loistavana lähtökohtana ymmärtää, kuinka pikalajittelu toimii Haskellissa.
Haskell-ohjelmointi ja Quicksort
Haskellin pikalajittelun tyylikkyys ja yksinkertaisuus tukevat toiminnallisen ohjelmoinnin vahvuuksia. Koodin tiiviys viittaa myös Haskellin tehokkaisiin listatoimintoihin.
Haskellin staattinen kirjoittaminen estää monia mahdollisia virheitä käännösvaiheessa, kun taas sen puhtaus (ei sivuvaikutuksia) ja laiska arviointi (laskutoimituksia ei suoriteta ennen kuin niitä tarvitaan) helpottavat suuresti koodin päättelyä ja optimointia.
Viime kädessä Quicksort ei ole vain tehokas lajittelualgoritmi, vaan osoitus toiminnallisen ohjelmoinnin voimasta ja Haskellin vahvuuksista kielenä.
