main = asText (qsort [3,9,1,8,5,4,7])
qsort lst =
case lst of
x:xs -> qsort (filter ((>=)x) xs) ++ [x] ++ qsort (filter ((<)x) xs)
[] -> []
{---------------------
QuickSort works as follows:
- Choose a pivot element which be placed in the "middle" of the sorted list.
In our case we are choosing the first element as the pivot.
- Gather all of the elements less than the pivot (the first filter).
We know that these must come before our pivot element in the sorted list.
Note: ((>=)x) === (\y -> (>=) x y) === (\y -> x >= y)
- Gather all of the elements greater than the pivot (the second filter).
We know that these must come after our pivot element in the sorted list.
- Run `qsort` on the lesser elements, producing a sorted list that contains
only elements less than the pivot. Put these before the pivot.
- Run `qsort` on the greater elements, producing a sorted list. Put these
after the pivot.
Note that choosing a bad pivot can have bad effects. Take a sorted list with
N elements. The pivot will always be the lowest member, meaning that it does
not divide the list very evenly. The list of lessers has 0 elements
and the list of greaters has N-1 elemens. This means qsort will be called
N times, each call looking through the entire list. This means, in the worst
case, QuickSort will make N^2 comparisons.
----------------------}