implement quicksort in SML with these requirements type (''a * ''a ->bool) -> ''alist -> ''a list example: quicksort (op >) [1, 6,2, 3, 4] = [6, 4, 3, 2,1] quicksort (op <)["beet", "bear","bank"] = ["bank","bear", "beet"] Quicksort is a sorting method that uses pivot. See the full description below. fun pivot(value, nil) = (nil,nil,nil) | pivot (value, first :: others) = let val (smalls,equals,bigs) = pivot(value, others) in if first < value then (first::smalls,equals,bigs) else if first = value then (smalls,first::equals,bigs) else (smalls,equals,first::bigs) end; Quicksort. Quicksort sorts by recursively pivoting the values around the first element (the pivot), then appending the resulting lists together. Example: [5, 1, 6, 2, 9, 0, 2, 6] pivot = 5 [1, 2, 0, 2][5][6, 9, 6]//recursion on first and third lists pivot = 1//pivot = 6 [0][1][2, 2][5][6, 6][9]//recursion on third and fifth lists pivot=2/pivot=6 [0][1][2][2][5][6][6][9] Append the lists together: [0, 1, 2, 2, 5, 6, 6, 9]
implement quicksort in SML with these requirements
type (''a * ''a ->bool) -> ''alist -> ''a list
example:
quicksort (op >) [1, 6,2, 3, 4] = [6, 4, 3, 2,1]
quicksort (op <)["beet", "bear","bank"] = ["bank","bear", "beet"]
Quicksort is a sorting method that uses pivot. See the full description below.
fun pivot(value, nil) = (nil,nil,nil)
| pivot (value, first :: others) =
let
val (smalls,equals,bigs) =
pivot(value, others)
in
if first < value then (first::smalls,equals,bigs)
else if first = value then (smalls,first::equals,bigs)
else (smalls,equals,first::bigs)
end;
Quicksort.
Quicksort sorts by recursively pivoting the values around the first element (the pivot), then appending the resulting lists together.
Example:
[5, 1, 6, 2, 9, 0, 2, 6]
pivot = 5
[1, 2, 0, 2][5][6, 9, 6]//recursion on first and third lists
pivot = 1//pivot = 6
[0][1][2, 2][5][6, 6][9]//recursion on third and fifth lists
pivot=2/pivot=6
[0][1][2][2][5][6][6][9]
Append the lists together: [0, 1, 2, 2, 5, 6, 6, 9]
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
