{-
Íàïèøèòå ðåàëèçàöèþ ôóíêöèè qsort. Ôóíêöèÿ qsort äîëæíàÿ ïðèíèìàòü íà âõîä ñïèñîê ýëåìåíòîâ è ñîðòèðîâàòü åãî â ïîðÿäêå âîçðàñòàíèÿ ñ ïîìîùüþ ñîðòèðîâêè Õîàðà: äëÿ êàêîãî-òî ýëåìåíòà x èçíà÷àëüíîãî ñïèñêà (îáû÷íî âûáèðàþò ïåðâûé) äåëèòü ñïèñîê íà ýëåìåíòû ìåíüøå è íå ìåíüøå x, è ïîòîì çàïóñêàòüñÿ ðåêóðñèâíî íà îáåèõ ÷àñòÿõ.

GHCi> qsort [1,3,2,5]
[1,2,3,5]
Ðàçðåøàåòñÿ èñïîëüçîâàòü òîëüêî ôóíêöèè, äîñòóïíûå èç áèáëèîòåêè Prelude.
-}

module Demo where

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (p:xs) = (qsort lesser) ++ [p] ++ (qsort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

-- https://wiki.haskell.org/Introduction#Quicksort_in_Haskell