Sort a binary array in one iteration

Given an array with only 0’s and 1’s , sort it in linear time.

Example Input: 1, 0, 1, 0, 1, 1, 0 0
Expected Output: 0, 0, 0, 0, 1, 1, 1, 1

This problem is similar to Move all zeros present in the array to the end and we can solve it using the same technique.

The only difference is that in the earlier problem, we were asked to move zeros to the end, in this problem we would have to move zeros to the front.

We can solve this easily by storing the index of the position where we need to store the next element and then swapping the zeros that we find as shown in the code below:

Solution Implementation

• C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int swap(vector<int>& vec, int first, int second) {
    int temp = vec[first];
    vec[first] = vec[second];
    vec[second] = temp;
}

int main() {
    vector<int> vec = {1, 0, 1, 0, 1, 1, 0, 0};
    int i = -1;
    for(int j = 0; j < vec.size(); j++) {
        if (vec[j] == 0) {
            i++;
            swap(vec, i, j);
        }
    }

    for(int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << "\n";
}