Introduction
This blog will discuss the approach to sorting an array containing 0s,1s, and 2s. Before jumping on the approach to the problem, let us first understand the problem.
Problem Statement
Given an array of 0s,1s and 2s, we have to sort the array in ascending order, i.e., 0s come first, then 1s, and finally 2s. Note that the array does not contain any other elements than these three.
Sample Example
Input : [1,0,0,2,1,0,1]
Output : [0,0,0,1,1,1,2]
Approach-1
This problem is a variation of the famous problem, Dutch National Flag Problem. In this approach, the array is divided into four sections,
- arr[0...to…LOW-1] (Zero)
- arr[LOW…to…MID-1] (One)
- arr[MID…to…HIGH] (unknown)
- arr[HIGH+1…to…N-1] (two)
If the ith element is 0, then swap it with low range, which in turn reduces the unknown range. Similarly, if the ith element is 1, then simply reduce the unknown range, and finally, if the ith element is 2, then swap it with the element in the high range.
Steps of Algorithm
Step 1: Maintain three indices as low = 0,mid = 0 and high = n-1
Step 2: Traverse the array from start to end while mid is less than equals to high
Step 3: If the element at index mid is 0, then swap it with the element at index low. Simultaneously increment the index of low and mid-index.
Step 4: If the element at index mid is 1,then shrink the unknown range, i.e , increment the mid index(mid = mid + 1).
Step 5: If the element at index mid is 2, then swap it with the element at index high. simultaneously decrease the index of high(high = high - 1).
Step 6: Print the array.
Implementation in C++
// c++ program to sort the array of 0,1,2 in one go.
#include <bits/stdc++.h>
using namespace std;
// function to sort the array of 0,1,2.
void sortArr(int arr[], int n)
{
int low = 0, mid = 0, high = n - 1;
while (mid <= high)
{
// if the middle element is 0.
if (arr[mid] == 0)
{
swap(arr[mid++], arr[low++]);
}
// if the middle element is 1.
else if (arr[mid] == 1)
{
mid++;
}
// if the middle element is 2.
else
{
swap(arr[mid], arr[high--]);
}
}
}
// main function.
int main()
{
// input array arr.
int arr[] = {1, 0, 0, 2, 1, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
// call of sort function
sortArr(arr, n);
// printing the resultant array after sorting.
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
Output :
[0,0,0,1,1,1,2]
Complexity Analysis
Time Complexity : O(n)
Since only one traversal is performed in total which costs O(n) time ,other operations are of constant time complexity, therefore total time complexity would be of the order O(n).
Space Complexity : O(1)
As no extra space is required apart from the given space, therefore the space complexity would be of the order O(1).
84+ registered