Quicksort je popularan algoritam za sortiranje, poznat po impresivnoj vremenskoj složenosti O(n log n) i strategiji 'Zavadi pa vladaj'. U suštini radi tako što odabire 'pivot' element iz niza i dijeli ostale elemente u dvije kategorije – one manje od pivota i one veće od njega. Ovaj proces uspješno postavlja pivot na njegovu stvarnu poziciju unutar sortiranog niza.
Kada se razvije u čisto funkcionalnom jeziku kao što je Haskell, njegova implementacija može biti sažeta i elegantna uz održavanje visokih performansi. Zahvaljujući Haskell-ovom jedinstvenom pristupu funkcionalnom programiranju, brzo sortiranje se može implementirati u samo nekoliko redova.
Rješenje sa Quicksort
Rješenje koje pruža algoritam brzog sortiranja je posebno dobro za skupove podataka koji slijede 'randomizirani' redoslijed i nisu jako iskrivljeni. Efikasnost i elegancija brzog sortiranja leži u redoslijedu operacija – počevši od odabira osovine, pa do posljedične particije.
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]. Ovo pokazuje da funkcija quicksort uzima listu elemenata koji se mogu naručiti i vraća drugu listu istog tipa elemenata.
Sam kod počinje s osnovnim slovima, brzo sortiranje [] = []. Ovo jednostavno kaže da je sortirana verzija prazne liste još jedna prazna lista.
Ključni dio funkcije brzog sortiranja je korak rekurzije. Ovaj korak koristi ljepotu podudaranja uzoraka u Haskell-u. Slučaj brzo sortiranje (pivot:rest) zauzima stožer (glava) i ostatak (rep) liste i upravo ovaj korak deli listu na dva dela.
Nakon toga, funkcija filtrira sve elemente manje od pivota u listu po imenu manja, i svi elementi veći ili jednaki pivot u drugu listu pod nazivom veće.
Na kraju, rekurzivno sortira manju i veću listu i kombinuje ove dvije, sa stožerom u sredini.
Funkcionalna suština Haskell-a
Quicksort odlično ilustruje snagu i ljepotu funkcionalnog programiranja s Haskell-om. Funkcije poput filtera, koji uzima predikat i listu i vraća listu elemenata koji zadovoljavaju predikat, čine algoritam brzog sortiranja jednostavnim i jasnim.
Također, rekurzivna priroda Haskell-a, kao što se vidi u definiciji brzog sortiranja na manje i veće, glatko izvršava koncept 'Zavadi pa vladaj' na kojem se brzo sortiranje zasniva.
Haskell biblioteke i funkcije višeg reda uvelike pomažu u tome da kod bude sažet i izražajan. Urođeno statičko kucanje pomaže u stvaranju sigurnijeg i predvidljivijeg koda.
Udruživanje elegancije i efikasnosti
U zaključku, brzo sortiranje u Haskell-u je odličan primjer kako funkcionalno programiranje može spojiti eleganciju i efikasnost. Uprkos svojoj jednostavnosti, to je moćan algoritam za sortiranje pogodan za širok spektar zadataka.
Vrijedi napomenuti, međutim, da iako je brzo sortiranje općenito brzo, njegove performanse mogu biti ranjive na određenim skupovima podataka (npr. kada je ulazna lista već sortirana). Stoga uvijek uzmite u obzir specifične zahtjeve i kontekst vašeg zadatka kada odlučujete koji algoritam za sortiranje ćete koristiti.
