Quicksort je jedan od najefikasnijih algoritama za sortiranje, koji se može pohvaliti prosječnom vremenskom složenošću od O(n log n). Zasnovano na metodologiji zavadi pa vladaj, pokazuje impresivne performanse pri sortiranju velikih skupova podataka. Izumio ga je britanski informatičar Tony Hoare 1959. i objavio 1961. godine, brzo sortiranje je postalo temeljni dio računarske nauke i programiranja..
Quicksort's popularnost je takođe posledica njegove lakoće implementacije u različitim programskim jezicima. U ovom članku ćemo se pozabaviti time kako se brzo sortiranje može implementirati pomoću Haskell programskog jezika, statički tipiziranog funkcionalnog programskog jezika poznatog po svojoj čistoći, sažetosti i eleganciji.
Kako funkcionira Quicksort?
Quicksort radi tako što odabire 'pivot' iz skupa podataka i dijeli ostale elemente u dvije grupe – one manje od pivota i one veće od pivota. Ovaj korak, poznat kao 'particioniranje', izvodi se rekurzivno dok se lista ne sortira.
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
Gornji Haskell kod počinje definisanjem osnovnog slučaja za praznu listu, koja vraća praznu listu. Za listu koja nije prazna, odabire stožer (u ovom slučaju, prvi element liste), a zatim filtrira ostatak liste u dvije podliste – jednu s elementima manjim od stožera, a drugu s elementima većim od ili jednaka osovini.
Razumijevanje Haskell implementacije
U našoj implementaciji Haskell-a, koristimo moćno jezično razumijevanje liste i funkcije višeg reda.
Linija koda `(brzo sortiranje manje) ++ [p] ++ (brzo sortiranje veće)` koncizno hvata suštinu brzog sortiranja – rekurzivno sortira i `manje` i `veće` podliste, a zatim spaja ove sortirane podliste sa stožerom u sredini. Ovo je strategija zavadi pa vladaj u akciji.
Uprkos svojoj jednostavnosti, ova implementacija može biti neefikasna za veće liste, jer filtrira svaku podlistu dvaput. Bez obzira na to, služi kao odlična polazna tačka za razumevanje kako brzo sortiranje funkcioniše u Haskelu.
Haskell programiranje i brzo sortiranje
Elegancija i jednostavnost brzog sortiranja u Haskellu podupiru snagu funkcionalnog programiranja. Sažetost koda takođe ukazuje na moćne Haskellove operacije sa listama.
Haskell-ovo statičko kucanje sprječava mnoge potencijalne greške u vrijeme kompajliranja, dok njegova čistoća (bez nuspojava) i lijena evaluacija (proračuni se ne izvršavaju dok nije potrebno) uvelike olakšavaju razmišljanje i optimizaciju koda.
Na kraju krajeva, brzo sortiranje nije samo efikasan algoritam za sortiranje već svedočanstvo moći funkcionalnog programiranja i prednosti Haskell-a kao jezika.
