Why don’t you give a try to solve the problem by yourself before reading the article from here are array Sort 0 1 2? Please make sure you try at least once it will help you understanding more.
The Dutch national flag problem is a problem in computer science programming proposed by Edsger Dijkstra. The flag of Netherland has three colours: white, red, and blue. Now you’re given balls of three colours which are arranged randomly in a line (count of balls doesn’t matter). Now your task is to randomly arrange balls of three colours such that balls of the same colour are placed together while on the other hand if we compare it to another problem. You may see this problem at Google, Palantir, PayPal and Zillow.
Consider an array think like you have an array of n elements which consists of elements 0,1, and 2 and you have to make an arrangement such that array is sorted or in other words, all 0’s, 1’s, and 2’s are together. Here, we will use the integers 0 for representing red colour, 1 for white and 2 to represent the colour blue respectively.
For example, Consider an array, A= [2,0,2,1,0,1,0,2]. After sorting array would become like this [0,0,0,1,1,2,2,2].
One way of solving this problem with the help of sorting algorithms such as merge-sort or quick-sort as we also know there are inbuilt sorting functions in C++/Java/Python which are hybrid of merge and insertion sort which would get us the final answer in a relatively fine way. It has a time complexity of O(nlogn), where n is the number of total items in the array.
So the easier solution would involve iterating through the original array and count the number of colored objects and just overwriting the original array in a second pass.
For solving this problem, I would suggest you to brushing up on quicksort. If you remember, the partition step of quicksort has some interesting effects. In the partition step, we choose a pivot element and all the elements smaller than it is shifted to the left of it and greater elements than pivot element are placed to the right. Don’t remember? Don’t worry here’s a look at the algorithms.
Solution 1: Two-Pass algorithm
Array = [0, 1, 2, 0, 2, 1, 1] Pivot Index = 1 Value at pivot index is 1. Forward pass: (Searching to place items less than 1) When, i = 0 [0, 1, 2, 0, 2, 1, 1] Swap index 0 with index 0 When, i = 1 [0, 1, 2, 0, 2, 1, 1] (no swap) When, i = 2 [0, 1, 2, 0, 2, 1, 1] (no swap) When, i = 3 [0, 0, 2, 1, 2, 1, 1] Swap index 1 with index 3 When, i = 4 [0, 0, 2, 1, 2, 1, 1] (no swap) When, i = 5 [0, 0, 2, 1, 2, 1, 1] (no swap) When, i = 6 [0, 0, 2, 1, 2, 1, 1] (no swap) After backwards pass: (Searching to place items greater than 1) When, i = 6 [0, 0, 2, 1, 2, 1, 1] (no swap) When, i = 5 [0, 0, 2, 1, 2, 1, 1] (no swap) When, i = 4 [0, 0, 2, 1, 1, 1, 2] Swap index 4 and index 6 When, i = 3 [0, 0, 2, 1, 1, 1, 2] (no swap) When, i = 2 [0, 0, 1, 1, 1, 2, 2] Swap index 2 and index 5 When, i = 1 [0, 0, 1, 1, 1, 2, 2] (stop* as the array is sorted)
Using this idea we can solve this problem with 2 passes O(~2N) time complexity and O(1) space. Here’s the python code:
Solution 2: Three-Way Partitioning (Single pass)
So in the worst case, for each item, we need to do extra logn amount of work to be able to complete the sort. And we know that worst-case space complexity for the merge sort is O(n), which we don’t want. Could you think of another approach which will help in solving the problem with one-pass using only constant space?
So the one thing that comes into our mind after solving the problem from the above approach is, “Can we have a more efficient algorithm than using these conventional sorting algorithms?” The answer is yes. We can take advantage of the fact there are just 3 distinct values scattered in the array.
Let’s try to change that partition function such that our colours get organised in one pass. Let’s try to analyse this situation as shown in the figure below:
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.
we are going to swap array elements around so that we don’t have to use extra space. For this, we are using 3-pointers as the name suggests there will be three-pointers low, mid, and high. With the help of “pointers”, we’ll be able to sort the array by swapping the value in constant time.
- Time complexity O(n): As we are performing the sorting in one traversal, the time it takes to execute the algorithm is in O(n).
- Space complexity O(1): We swap elements we traverse the array so we don’t need any extra space. Hence, space complexity is O(1).
Solution 3: Brute Force
If you’re the lazy one and don’t want to learn any algorithm then there is a brute force approach for you, we know there are only 3 elements 0,1, and 2. This gives us a hint:
- Start with declaring three variable assuming count0, count1, and count2 with initialising these with zero.
- Now traverse the whole array once counting the no. of 0’s,1’s, and 2’s with increasing the particular count. After traversal of the array, you have a count of 0’s,1’s, and 2’s in the array.
- Make a new variable say k=0 and traverse the array once again with updating the value of the array with 0’s first, then 1’s and finally with 2’s. So your final array will have sorted 0’s,1’s, and 2’s.
Here’s the C++ code for the same:
As we can see there are n elements in the array and total two traversals are made so we know for traversal of an array consisting of n elements requires time complexity to be O(n) and same complexity for the second traversal so the overall complexity of the algorithm comes down to O(n) + O(n) = 2*O(n) and 2 is a constant so the overall time complexity is O(n) while we didn’t use any extra space, so the space complexity of the code is O(1). But don’t worry if you didn’t understand the time/space complexity then we have got something for you check here What is Big O notation? | Coding Ninjas Blog.
If you already know the quick-sort algorithm then you must have got the meme but if not then don’t worry not only quick sort but you can learn many more sorting algorithms from here Sorting in Data Structure: Categories & Types | Coding Ninjas Blog.
This algorithm tells us about the quick-sort as it used there because that partitioning part is the core thing in quick-sort. But One thing we learnt here in this algorithm is to deal with time complexity like how we brought time complexity from O(nlogn) to O(n) using 3-partitioning. Because we know one thing finding solution is not enough but finding an optimal solution is also necessary wherever possible.