Sorting is a fairly major topic of study when it comes to programming, and there are tons of ways to do it. I don’t know how interesting these algorithms are to other people, but they have always been an interest of mine. I think they’re neat because they illustrate that there can be several ways to tackle even the simplest of tasks (which, in my opinion, is one of the things that makes programming so fun!).
Since I’m always looking for new things to try, I’ve decided to take a few of the common sorting algorithms and implement them on my own in Haskell. For those of you who aren’t familiar with it, here’s a brief overview.
Back to the point of the blog post. I’ll be covering how to implement three sorting algorithms in a functional manner: Bubble Sort, Insertion Sort, and finally, Quicksort. If you don’t have a background in Haskell, this might all come off as programming jargon, but if you’re looking for an interesting new look at these algorithms you’ve seen a billion times implemented imperatively, or are interested in picking up Haskell as a hobby or something, I’d recommend reading on.
The bubble sort algorithm is as follows:
bubbleSort :: (Ord a) => [a] -> [a] bubbleSort  =  bubbleSort [x] = [x] bubbleSort (x:y:xs) = if sorted thisSort then thisSort else bubbleSort thisSort where thisSort = (min x y) : bubbleSort ((max x y):xs) sorted :: (Ord a) => [a] -> Bool sorted  = True sorted [x] = True sorted (x:y:xs) = if x <= y then sorted (y:xs) else False
Rather long, but effective. Bubble Sort isn’t the most efficient sorting algorithm, especially since it has to do all of that checking if it’s already sorted. I’m not a big fan of this one.
Insertion sort is pretty simple to follow. We start with an array, as always, and then follow these steps:
import Data.List insertionSort :: (Ord a) => [a] -> [a] insertionSort = foldr insert 
How elegant is that? This could take many lines in an imperative language, but we make use of Haskell’s recursive
foldr method to populate our sorted list, and the appropriately named function
insert taken from the Data.List package helps us to populate it in the exact manner we’re looking for.
The Quicksort algorithm can be pretty intimidating, especially at first glance. This is because it makes use of recursion to accomplish it’s sorting, which is a particularly tough concept to fully understand when it comes to programming. The instructions for Quicksort look a little something like this:
(I would recommend reading up on this algorithm if the above instructions do not make sense; I am not the best at explaining things) Sounds complicated, right? Here’s a Haskell implementation:
quickSort :: (Ord a) => [a] -> [a] quickSort  =  quickSort (x:xs) = quickSort smaller ++ [x] ++ quickSort larger where smaller = filter (<=x) xs larger = filter (> x) xs
What? It only takes five lines to implement Quicksort? This is why Haskell is so cool to me. Compare this with something like, say, a Java implementation, and you’ll see what I mean. It’s just so simple! We’re simply defining
quickSort as a quickSorted list of smaller numbers concatenated with a singleton list containing a pivot, concatenated with a quickSorted list of larger numbers. Easy to read, though the algorithm may seem pretty complicated at first glance.
Hope you enjoyed the read!