Sorting algorithms in Haskell
In earlier posts, I looked at construction of merge sort, quick sort and insertion sort algorithms in an imperative language. Besides the fact that the overall code is longer in imperative, it would take me even longer to read and comprehend the logic. Code readability is another area where functional languages shine. Let's see how these algorithms are written in Haskell.
Here we divide the problem into two parts:
- instead of sorting the entire list in one go, divide the list into two and sort those
- merge two lists that are already sorted
merge :: Ord a => [a] -> [a] -> [a] merge  l = l merge l  = l merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys msort :: Ord a => [a] -> [a] msort  =  msort [x] = [x] msort l = merge (msort left) (msort right) where left = take half l right = drop half l half = (length l) `div` 2
Here, we choose the first element of the list as pivot. Then we split the tail into two lists - a list with elements that are smaller than or equal to pivot and a list with elements that are larger than the pivot. We sort these two lists using quick sort and append the smaller element list to the left side of pivot and larger element list to the right side of pivot.
qsort :: Ord a => [a] -> [a] qsort  =  qsort [x] = [x] qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger where smaller = [s | s <- xs, s <= x] larger = [l | l <- xs, l > x]
Here again, we divide the problem into two parts:
- sort the tail of list using insertion sort
- insert the head at the appropriate position of the sorted tail such that the resulting list is still sorted.
insert :: Ord a => a -> [a] -> [a] insert x  = [x] insert x (y:ys) | x <= y = x : y : ys | otherwise = y : insert x ys isort :: Ord a => [a] -> [a] isort  =  isort [x] = [x] isort (x:xs) = insert x (isort xs)
Besides the clear intention of what the algorithm is doing, the code is also beautiful. Furthermore, note that all algorithms are polymorphic - not only they work with number of different kinds, they work with any type that is an instance of
Ord class -
Bool and lists, tuples containing these types! This is indeed powerful. I am liking functional languages!
*Main> isort [True, False] [False,True] *Main> msort ["hello", "aloha"] ["aloha","hello"] *Main> qsort "hello" "ehllo" *Main> msort [6,5..1] [1,2,3,4,5,6]