Quicksort je popularan algoritam za sortiranje, poznat po svojoj impresivnoj vremenskoj složenosti od O(n log n) i strategiji "Podijeli pa vladaj". U suštini funkcionira odabirom 'pivot' elementa iz niza i particioniranjem ostalih elemenata u dvije kategorije – one manje od stožera i one veće od njega. Ovaj proces uspješno postavlja stožer na njegov stvarni položaj unutar sortiranog niza.
Kada se razvija u čisto funkcionalnom jeziku kao što je Haskell, njegova implementacija može biti sažeta i elegantna uz zadržavanje visokih performansi. Zahvaljujući Haskellovom jedinstvenom pristupu funkcionalnom programiranju, brzo sortiranje može se implementirati u samo nekoliko redaka.
Rješenje uz Quicksort
Rješenje koje nudi algoritam za brzo razvrstavanje posebno je dobro za skupove podataka koji slijede 'slučajni' redoslijed i nisu jako iskrivljeni. Učinkovitost i elegancija brzog sortiranja leži u redoslijedu operacija – počevši od odabira stožera i posljedičnog particioniranja.
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (pivot:rest) = quicksort lesser ++ [pivot] ++ quicksort greater
where
lesser = filter (< pivot) rest
greater = filter (>= pivot) rest
Objašnjenje korak po korak
Kod počinje deklaracijom tipa, brzo sortiranje :: Red a => [a] -> [a]. To pokazuje da funkcija quicksort uzima popis elemenata koji se mogu naručiti i vraća drugi popis iste vrste elemenata.
Sam kod počinje s osnovnim slučajem, brzo sortiranje [] = []. Ovo jednostavno kaže da je sortirana verzija praznog popisa još jedan prazan popis.
Ključni dio funkcije brzog sortiranja je korak rekurzije. Ovaj korak koristi ljepotu podudaranja uzoraka u Haskell-u. Slučaj brzo sortiranje (zaokret:ostatak) zauzima stožer (glavu) i ostatak (rep) popisa i ovaj korak dijeli popis na dva dijela.
Nakon toga, funkcija filtrira sve elemente manje od pivota u popis prema imenu manji, a sve elemente veće ili jednake zaokretnoj točki u drugu imenovanu listu veća.
Na kraju, rekurzivno razvrstava manje i veće popise i kombinira ova dva, sa pivotom u sredini.
Funkcionalna suština Haskella
Quicksort izvrsno ilustrira snagu i ljepotu funkcionalnog programiranja s Haskell-om. Funkcije poput filtera, koji uzima predikat i popis i vraća popis elemenata koji zadovoljavaju predikat, čine algoritam brzog sortiranja jednostavnim i jasnim.
Također, rekurzivna priroda Haskella, kao što se vidi u definiciji brzog razvrstavanja na manje i veće, glatko izvršava koncept 'Podijeli pa vladaj' na kojem se temelji brzo razvrstavanje.
Haskell biblioteke i funkcije višeg reda uvelike pomažu u izradi koda sažetog i izražajnog. Inherentno statično tipkanje pomaže u stvaranju sigurnijeg i predvidljivijeg koda.
Spajanje elegancije i učinkovitosti
U zaključku, brzo sortiranje u Haskellu je najbolji primjer kako funkcionalno programiranje može spojiti eleganciju i učinkovitost. Unatoč svojoj jednostavnosti, to je moćan algoritam za sortiranje prikladan za širok raspon zadataka.
Međutim, vrijedi napomenuti da iako je brzo sortiranje općenito brzo, njegova izvedba može biti ranjiva na određenim skupovima podataka (npr. kada je ulazni popis već sortiran). Stoga uvijek uzmite u obzir specifične zahtjeve i kontekst svog zadatka kada odlučujete koji ćete algoritam sortiranja koristiti.
