Quicksort on üks tõhusamaid sortimisalgoritme, mille keskmine ajaline keerukus on O(n log n). Jaga ja valluta metoodikale tuginedes on see suurte andmekogumite sortimisel muljetavaldav. Briti arvutiteadlase Tony Hoare’i 1959. aastal leiutatud ja 1961. aastal avaldatud kiirsortimisest on saanud arvutiteaduse ja programmeerimise põhiosa..
Quicksort's populaarsus on tingitud ka selle hõlpsast rakendamisest erinevates programmeerimiskeeltes. Selles artiklis uurime, kuidas kiirsortimist saab rakendada, kasutades Haskelli programmeerimiskeelt, staatiliselt tipitud funktsionaalset programmeerimiskeelt, mis on tuntud oma puhtuse, lakoonilisuse ja elegantsi poolest.
Kuidas Quicksort töötab?
Quicksort toimib, valides andmestikust „pivoti” ja jagades teised elemendid kahte rühma – need, mis on pivotist väiksemad ja need, mis on pivotist suuremad. Seda etappi, mida nimetatakse "partitsioneerimiseks", viiakse läbi rekursiivselt, kuni loend on sorteeritud.
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
Ülaltoodud Haskelli kood algab tühja loendi põhitähe määratlemisega, mis tagastab tühja loendi. Mittetühja loendi jaoks valib see pivoti (antud juhul loendi esimese elemendi), seejärel filtreerib ülejäänud loendi kaheks alamloendiks – ühes, mille elemente on pivotist vähem, ja teises, mille elemendid on suuremad kui või võrdne pöördega.
Haskelli juurutamise mõistmine
Haskelli teostuses kasutame keele võimsat loendi mõistmist ja kõrgema järgu funktsioone.
Koodirida `(kiiresorti väiksem) ++ [p] ++ (kiiresortimine suurem)” kajastab lühidalt kiirsortimise olemust – see sorteerib rekursiivselt nii väiksemad kui ka suuremad alamloendid, seejärel ühendab need sorteeritud alamloendid pivotiga. keskel. See on jaga ja valluta strateegia tegevuses.
Vaatamata oma lihtsusele võib see rakendus olla suuremate loendite puhul ebaefektiivne, kuna see filtreerib iga alamloendi kaks korda. Sellegipoolest on see suurepärane lähtepunkt, et mõista, kuidas kiirsortimine Haskellis töötab.
Haskelli programmeerimine ja kiirsort
Haskelli kiirsortimise elegants ja lihtsus toetavad funktsionaalse programmeerimise tugevaid külgi. Koodi kokkuvõtlikkus viitab ka Haskelli võimsatele loenditoimingutele.
Haskelli staatiline tippimine hoiab ära paljud võimalikud vead kompileerimise ajal, samas kui selle puhtus (kõrvalmõjudeta) ja laisk hindamine (arvutusi ei teostata enne, kui see on vajalik) hõlbustavad oluliselt koodi arutlemist ja optimeerimist.
Lõppkokkuvõttes pole kiirsortimine lihtsalt tõhus sortimisalgoritm, vaid tunnistus funktsionaalse programmeerimise võimsusest ja Haskelli kui keele tugevatest külgedest.
