_MVP_
C give all more thought
- Joined
- Jul 15, 2022
- Posts
- 55,294
- Reputation
- 58,048
import Data.List (partition)
qsort x = qsortSub x x
-- minimum case
qsortSub [] as = as -- shows termination
-- standard qsort cases
qsortSub (l:ls) [] = [] -- nonrecursive, so accepted
qsortSub (l:ls) [a] = [a] -- nonrecursive, so accepted
qsortSub (l:ls) (a:as) = let (lesser, greater) = partition (<a) as
-- recursive, but recurs on ls, which is a substructure of
-- its first input.
in qsortSub ls lesser ++ [a] ++ qsortSub ls greater
qsort x = qsortSub x x
-- minimum case
qsortSub [] as = as -- shows termination
-- standard qsort cases
qsortSub (l:ls) [] = [] -- nonrecursive, so accepted
qsortSub (l:ls) [a] = [a] -- nonrecursive, so accepted
qsortSub (l:ls) (a:as) = let (lesser, greater) = partition (<a) as
-- recursive, but recurs on ls, which is a substructure of
-- its first input.
in qsortSub ls lesser ++ [a] ++ qsortSub ls greater
