Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Dutch National Flag Problem
3.
Solution 1: Two-Pass algorithm
4.
Solution 2: Three-Way Partitioning (Single pass)
5.
COMPLEXITY:
6.
Solution 3: Brute Force
6.1.
Here’s the C++ code for the same:
7.
Frequently Asked Questions
7.1.
What is an Array?
7.2.
What is Quick Sort?
7.3.
What is Merge Sort?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sort An Array Containing 0’s, 1’s and 2’s

Author Ayush Mishra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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. If after reading you didn't understand then this blog will help you to understand the problem of sorting an array of 0's, 1's, and 2's.

sort an array

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Dutch National Flag Problem

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]. 

sorting_array

Image Source:- leetcode

One way of solving this problem is 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 the pivot element are placed to the right.

Don’t remember?

Don’t worry here’s a look at the algorithms.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution 1: Two-Pass algorithm

Two_Pass_algorithm

Image Source: ytimg.com

Example:

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:

sorting_array

Solution 2: Three-Way Partitioning (Single pass)

So in the worst case, for each item, we need to do an extra logn amount of work to be able to complete the sort. And we know that the worst-case space complexity for the merge sort is O(n), which we don’t want.

Could you think of another approach that 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:

sorting_array

Image Source: zunayed.dev

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.

Here’s the JavaScript code for the same:

Sorting_array

COMPLEXITY:

  • 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).
     

Also see, Morris Traversal for Inorder.

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:

sort_array

COMPLEXITY

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.

Frequently Asked Questions

What is an Array?

An array is a group of related data elements kept in close proximity to one another in memory. The only way to access each data element directly is by using its index number, making it the most basic data structure.

What is Quick Sort?

The popular sorting algorithm known as Quicksort sorts an array of n elements with an average of n log n comparisons. It is a sorting algorithm that is both quick and very effective. This algorithm employs the strategy of "divide and conquer."

What is Merge Sort?

Merge sort sorts the elements using a divide-and-conquer strategy, it is comparable to the quick sort algorithm. One of the most well-liked and effective sorting algorithms is it. It divides the provided list into two equal parts, makes calls for each half, and then joins the two sorted halves. 

Conclusion

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.

Recommended problems -

Previous article
Find a rotation with maximum hamming distance
Next article
Find the Maximum Sum of i*arr[i] Among all Possible Rotations of an Array
Live masterclass