Last Updated: 21 Oct, 2021
Sort Array of 0s and 1s.
Easy
Asked in companies
You are given an array ‘A’ of size ‘N’ containing only 0s and 1s. You have to sort the array by traversing the array only once.
For Example:
For the following array:
[0 1 1 1 0 0 1]
The output should be [0 0 0 1 1 1 1].
Note:
You have to sort the array in place.
Input Format:
The first line will contain a single integer ‘T’ denoting the number of test cases. Then the test cases follow.
The first line of each test case will contain a single integer ‘N’, denoting the size of the array.
The second line of each test case will contain ‘N’ space-separated integers, denoting the elements of the array.
Output Format:
For each test case, print the input array after sorting it.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 5
1 <= N <= 10^5
A[i] = 0 or 1
Time Limit: 1 sec.
Approaches
Count the number of 0s and 1s present in the input array. Suppose “count0” and “count1” be the number of 0s and 1s present respectively. Then replace the first “count0” elements in the array with 0 and the remaining elements with 1.
Algorithm:
- Declare an integer variable “count0” and initialize it with 0.
- Iterate over the array.
- If the current element is 0.
- Increment the “count0” variable.
- If the current element is 0.
- Iterate over the array from 0 to (“count0” - 1) and mark all the elements as 0.
- Iterate over the array from “count0” to (‘N’ - 1) and mark all the elements as 1.
We will put all the 0s to the left side. Hence all the 1s will be automatically pushed to the right side. For that, we will take two variables - one will traverse the array from the right and another from the left till they reach the same place. If the right one has 0 it will swap with the left one. Thus all the 0s will come towards the left side.
Algorithm:
- Declare two integer variables “index0” and “index1”.
- Set “index0” to 0 and “index1” to (‘N’ - 1).
- Start a while loop with the condition: “index0” < “index1”.
- If A[index1] is 0.
- Swap A[index1] with A[index0].
- Increment “index0”.
- Else
- Decrement “index1”.
- If A[index1] is 0.