Binary Array Sorting

Problem

Given a binary array A[] of size N. The task is to arrange the array in increasing order.

Note: The binary array contains only 0 and 1.

Examples:

Example 1:

Input: 
5
1 0 1 1 0

Output: 
0 0 1 1 1

Explanation: 
After arranging the elements in increasing order, elements will be as 0 0 1 1 1.

Example 2:

Input:
10
1 0 1 1 1 1 1 0 0 0

Output: 
0 0 0 0 1 1 1 1 1 1

Explanation: 
After arranging the elements in increasing order, elements will be 0 0 0 0 1 1 1 1 1 1.

Your task:

This is a function problem. You only need to complete the function binSort() that takes the array A[] and it's size N as parameters and sorts the array. The printing is done automatically by the driver code.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^6$
• $0<=A[i]<=1$

Solution

Python

def binSort(self, A, N): 
    j = -1
    for i in range(N):
        if A[i] < 1:
            j = j + 1
            A[i], A[j] = A[j], A[i]

Java

static void binSort(int A[], int N) {
    int j = -1;
    for (int i = 0; i < N; i++) {
        if (A[i] < 1) {
            j++;
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}

C++

void binSort(int A[], int N) {
    int j = -1;
    for (int i = 0; i < N; i++) {
        if (A[i] < 1) {
            j++;
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}

C

void binSort(int A[], int N) {
   int j = -1;
    for (int i = 0; i < N; i++) {
        if (A[i] < 1) {
            j++;
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$