quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = smaller ++ [x] ++ bigger
where smaller = quicksort [y| y <- xs , y < x]
bigger = quicksort [y | y <- xs, y >= x]
So how does this work?
- [a] ->[a] means that quicksort takes a list as input and returns a list as output
- (Ord a) means that a belongs to a type class Ord (i.e. a is an ordered type)
- The first expression means that quicksort returns an empty list for an input empty list
- The second expression works as follows. The input list is broken into its head and tail (x, xs). We use x as the pivot element. all elements smaller than x in xs are identified and sorted using quicksort itself (recursively). All elements greater than or equal to x are sorted by quicksort itself (recursively). The final result is smaller + [x] + bigger.
So here are some examples:
*Main> quicksort [2, 1, 3]
[1,2,3]
*Main> quicksort "i don't believe you"
" 'bdeeeiilnootuvy"
*Main> quicksort "i love you"
" eiloouvy"
*Main> quicksort [50, 40, 30 , 10, 20, 30, 40, 50, 20]
[10,20,20,30,30,40,40,50,50]
*Main>
