Wednesday, August 19, 2009

Quicksort in Haskell

Here is my attempt at quicksort in Haskell

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]
*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]