## Wednesday, August 19, 2009

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