“Fungorithms” is a blog series that I would like to introduce an algorithm I came across I found interesting. They are not necessarily difficult, but they are the building blocks of your next sophisticated algorithm. I want to share the “fun” by analyzing and discussing the algorithm.
The problem is pretty straightforward. We have 3 distinct values scattered in an array (or any container with the memory location, index), and we need to sort them. This algorithm is better known as “Dutch national flag problem” because the dutch flag has three colours: red, white and blue, and sorting these colours would complete the flag. As you may have noticed, having 3 distinct values here is the catch. That’s the critical assumption of our algorithm.
For example, here is a potential input array,
[2,0,2,1,0,1,0,2,1]. After we sort these values, we would get
One intuitive approach would be to apply one of the popular sorting algorithms such as merge-sort or quick-sort, which would get us the final answer in a relatively fine way. It works in the time complexity of , where n is the number of total items in the array. So in the worst case, for each item, we need to do extra amount of work to be able to complete the sort. The space complexity for the merge sort, by the way, is , which might not be something we want either.
So here is the famous question which comes to mind, “Can we have a more efficient algorithm than using these conventional sorting algorithms?”
The answer is yes. We can leverage the fact that there are just 3 distinct values scattered in the array.
The idea is quite simple. Track and Swap:
To avoid using any extra space, we are going to swap array elements around. To do this, we are going to need to keep pointers for each of the left-bucket, mid-bucket and right-bucket. The “pointers” will help us to sort by swapping array values in constant time. If we do not care about the extra space complexity, we can just use 3rd containers to group them in values and concatenate these at the end. However, this isn’t the cleanest solution obviously.
Time complexity O(n)
Space complexity O(1)
The code is provided in Python, which is a well-suited language for writing out algorithms. You can easily follow and understand their meanings because it obfuscated a lot of verbosities.
As you can see, we are looping the input array once to figure out the position and make necessary swaps to have the array sorted. Tracking the equal is important. Also, tracking the smallest and largest pointer from the end of the array is important.
This algorithm is repeatedly used in quick-sort because this task eventually is what quick sort does. Watch how
partition function is handled in quick sort. The code is not identical to above but fundamentality of the algorithm is pretty much the same.
The algorithm quite amusing because we just reduced time complexity down from to . Reducing the bits of complexity is always fun and challenging. Please be careful when reducing though, we still want the algorithm to function as expected.