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.
Most programming languages (Java, C++, Python, Ruby, Javascript, etc) are defined as imperative, which basically means that programs are executed line-by-line. Many of the aforementioned languages are also defined as object-oriented, meaning that virtually everything is a part of an object. I won’t get into the details about OOP here, since we’re talking about Haskell, but you can read about it if you’d like. Haskell differs from these languages by conforming to a paradigm in which everything is defined as a function. Objects are not present here, and iterative steps don’t quite work in the same way – nothing is being executed line-by-line – all instructions are defined in functions. This is a rather mind-blowing concept, but it’s extremely cool once you can get a mental grasp on it.
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!
-Ben