Last Updated: 17 Nov, 2020
Sort An Array of 0s, 1s and 2s
Easy
Asked in companies
You have been given an array/list 'arr' consisting of 'n' elements.
Each element in the array is either 0, 1 or 2.
Sort this array/list in increasing order.
Do not make a new array/list. Make changes in the given array/list.
Example :
Input: 'arr' = [2, 2, 2, 2, 0, 0, 1, 0]
Output: Final 'arr' = [0, 0, 0, 1, 2, 2, 2, 2]
Explanation: The array is sorted in increasing order.
Input Format:
The first line contains a positive integer ‘n’, which represents the length of the array/list.
The second line of each test case contains ‘n’ single space-separated integers representing the elements of the array/list.
Output Format:
The output will print ‘n’ single space-separated integers of the sorted array/list.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Approaches
Simply, we will sort the array.
A two-pass algorithm can easily solve the problem. We will count the number of 0s, 1s and 2s in the array/list.
Then, we will overwrite the array with the total number of 0s, followed by 1s and 2s, respectively.
We can sort the array in one-pass by maintaining three positional pointers ‘zeroPos’, ‘onePos’ and ‘twoPos’ initialised to 0, 0 and n - 1, respectively.
Here, ‘zeroPos’ represents the first 1 after all 0s, ‘onePos’ represents the current element, and ‘twoPos’ represents the last unexplored element before all 2s.
Now, we iterate through ARR with ‘onePos’-
- If we encounter a 0.
- We will swap arr[zeroPos] and arr[onePos].
- This is because ‘zeroPos’ represents the first 1 after all 0s and we have to ensure that all 0s must come before 1.
- Then increment ‘zeroPos’ and ‘onePos’ by 1.
- Else, If we encounter a 1.
- We will simply increment ‘onePos’ by 1.
- Else, If we encounter a 2.
- We will swap arr[onePos] and arr[twoPos].
- This is because ‘twoPos’ represents the last unexplored element before all 2s and we have to ensure that all 2s must come after 1.
- Then decrement ‘twoPos’ by 1.
Similar problems