Dutch national flag problem
Fungorithms
22 Feb 2020
View Comments
#programming
#fun
#algorithm
#series
#efficient
#sorting
#dutch
#flags
“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.
Sorting 3 values
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 [0,0,0,1,1,1,2,2,2].
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 \(O(nlogn)\), where n is the number of total items in the array. So in the worst case, for each item, we need to do extra \(logn\)amount of work to be able to complete the sort. The space complexity for the merge sort, by the way, is \(O(n)\), 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:
- First, we can start with the mid-value of the 3 values as a pivot.
- From that pivot (middle) value, we can place values less than pivot in the left of the pivot.
- Place values higher than pivot in the right of the pivot.
- If they are equal to the pivot (middle) value, we do pretty much nothing.
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.
Complexity
Time complexity O(n)
- Since we are doing the sorting in one pass of an ‘n’-item array, the time it takes to execute the algorithm is in \(O(n)\)
Space complexity O(1)
- We exchange elements as we progress as I described above, meaning we do not use any extra space to store these values. Hence, space complexity is \(O(1)\)
Code
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.
def sortColors(nums):
pivot = 1
smaller = 0
equal = 0
larger = len(nums) - 1
while (equal <= larger):
if pivot > nums[equal]:
tmp = nums[smaller]
nums[smaller] = nums[equal]
nums[equal] = tmp
smaller+=1
equal+=1
elif pivot == nums[equal]:
equal+=1
else:
tmp = nums[larger]
nums[larger] = nums[equal]
nums[equal] = tmp
larger-=1
nums = [0, 1, 2, 2, 1, 1, 2, 2, 0, 0, 0, 0, 2, 1]
print("Before Sort: ")
print(nums)
# [0, 1, 2, 2, 1, 1, 2, 2, 0, 0, 0, 0, 2, 1]
sortColors(nums)
print("After Sort: ")
print(nums)
# [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]Conclusion
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 \(O(nlogn)\) to \(O(n)\). 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.
