Given a binary array, sort it using one traversal and no extra space.
Examples :
Input : 1 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 0 0
Output : 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
Explanation: The output is a sorted array of 0 and 1
Input : 1 0 1 0 1 0 1 0
Output : 0 0 0 0 1 1 1 1
Explanation: The output is a sorted array of 0 and 1
Solution:
void sortBinaryArray(int nums[])
{
int j = -1;
for (int i = 0; i < nums.length; i++) {
// if number is smaller than 1
// then swap it with j-th number
if (a[i] < 1) {
j++;
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
Comments