Sort an Array of 0s 1s And 2s
FREE
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Problem Statement
We are given an array consisting of only 0s, 1s, and 2s. Our task is to write a program to sort the given array without using inbuilt functions.
Example
Example Explanation
Since we already know that an array is a linear data structure that contains data elements of the same data type at contiguous memory locations. For example, an array containing 12 elements as follows -[0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0].
Sorting an array means arranging of data elements in ascending or descending order, so our task here is to sort it in ascending order. Therefore, in our resultant sorted array, all 0s must come before all the 1s and all 1s must come before all 2s.
Thus, the sorted array will be [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2]
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreConstraints
1 <= n <= 10^6 , here n is the number of elements in the array A 0 <= A[i] <= 2 , here A[i] is the value of every ith element in the array A
Approach 1: By Brute force method using double traversal
-
Intuition: The first idea that comes into our mind since there are only 3 distinct values, is to just count the number of 0s, 1s and 2s. So we will be using 3 different variables to store these values which will be followed by overwriting the array with the help of these count variables.
This problem is similar to three-way partitioning for the Dutch national flag problem.
-
Algorithm:
- Initialize 3 variables count0, count1, count2 to store the count of 0s, 1s, and 2s respectively.
- Traverse through the array and increase count0 if the element is 0, increase count1 if the element is 1 and increase count2 if the element is 2.
- Now traverse the array again and overwrite the first count0 positions in the array with 0, the next count1 positions with 1, and the remaining count2 with 2.
-
Implementation
C++ Program to sort an array of 0s 1s and 2s using Brute Force method:
Java Program to sort an array of 0s 1s and 2s using Brute Force method:
Python Program to sort an array of 0s 1s and 2s using the Brute Force method:
Output
-
Complexity Analysis
In the above approach, we require traversing the array twice; once to count the number of 0s, 1s, and 2s. While the second traversal is required to store the values at their sorted places in the array, that means we need to copy all the n elements. T(n) = O(n) + O(n)
Hence, Time complexity will be - T(n) = O(n)
Also, we observe that no extra space is required to store the elements.
Hence, Space complexity will be - S(n) = O(1)
Turn Learning into Career Growth
Approach 2: By using a single traversal method named the three-way partitioning
-
Intuition: In this approach we will be using 3-pointers low, mid, high. We will use these pointers to place all 0s to the left end, all 2s to the right end, and all 1s in the middle of the array, hence making the array sorted.
-
Algorithm:
-
Initialize 3 pointers low = 0, mid = 0 and high = N-1.
-
Start traversing the array from start to end, repeat this process until mid <= high.
- If the A[mid]==0, then swap(A[low], A[mid]) and update the pointers low = low + 1 and mid = mid + 1.
- If the A[mid]==1, just update the pointer mid = mid + 1.
- If the A[mid]==2, then swap(A[mid], A[high]) and update the pointer high = high - 1
-
Print the sorted array
-
-
Implementation:
C++ Program to sort an array of 0s 1s and 2s using three-way partitioning:
Java Program to sort an array of 0s 1s and 2s using three-way partitioning:
Python Program to sort an array of 0s 1s and 2s using three-way partitioning:
Output
-
Complexity Analysis
In this approach, we require traversing the array only once for comparing the value present at mid index with 0, 1, and 2 and swapping them if necessary. After the traversal is done, the result will be a sorted array. T (n) = C + O (n)
Here C is the constant time taken for swapping the values in the variables.Hence Time complexity will be - T(n) = O(n)
Also, we observe that no extra space is required to store the elements.
Hence Space complexity will be - S(n) = O(1)
Conclusion
- In the first approach, we used a simple solution using the counting sort algorithm by counting the number of 0s, 1s, and 2s and then placing them in the array in their correct order.
- In the second approach, since we had only three distinct elements to be sorted, we divided the given array into four sections using three-pointers namely low, mid, and high.
- This problem of sorting 0s 1s and 2s is similar to three-way partitioning for the Dutch national flag problem.
- Comparison of Time and Space complexities for both approaches
- Brute force approach: Time = O(n), Space = O(1).
- Three-way partitioning: Time = O(n), Space = O(1).