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>

## No comments:

Post a Comment