Home » Data Structure » Array Data Structure

Sort an array that contains only 0's and 1's

C++ implementation to sort an array that contains only 0's and 1's.
Submitted by Vikneshwar GK, on January 20, 2022

Consider an array of size n and it contains values only 0's and 1's. For example, if n=5, the array elements can be 0, 1, 1, 0, and 1. The task at hand is to sort this array in a time-efficient manner, i.e., place all the 0's on the left side and 1's on the right side.

Example:

Input:
test1[] = {1, 1, 0, 1, 0, 0, 0, 1, 1, 0}
Output:
test1[] = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1}

Input:
test1[] = {1, 1, 1, 1, 1, 1, 0, 1, 1, 1}
Output:
test1[] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}

Solution 1: Sorting the array

This is a usual approach to solve this problem, i.e., sorting the given array using an O(nlog(n)) algorithm.

C++ Implementation:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
    cout << endl;
}

// Main function
int main()
{
    int array[100], N;
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    // sorting the array
    sort(array, array + N);

    cout << "Sorted Array" << endl;
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:0
Enter element 2:0
Enter element 3:1
Enter element 4:1
Enter element 5:0
Sorted Array
0 0 0 1 1 

Solution 2: Using start and end Pointers

This approach uses two pointers to point the start and end of the array. It involves the following steps:

• Step 1: start=0 and end=length-1
• Step 2: increment start if the array element at start is equal to 0.
• Step 3: if not, swap the elements at start and end, and decrement end.
• Step 4: repeat step 2 and step 3 until start becomes greater than or equal to end.

C++ Implementation:

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

// function to sorting 0 and 1
void sort0and1(int array[], int length)
{
    int start = 0;
    int end = length - 1;

    // loop until start is less than end
    while (start < end) {

        if (array[start] == 1) {
            // swap element at start and end
            swap(array[start], array[end]);
            end--;
        }
        else {
            start++;
        }
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
    cout << endl;
}

// Main function
int main()
{
    int array[100], length;
    cout << "Enter Number of elements: ";
    cin >> length;

    for (int i = 0; i < length; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    // sorting the array
    sort0and1(array, length);

    cout << "Sorted Array" << endl;
    printArray(array, length);

    return 0;
}

Output:

Enter Number of elements: 10
Enter element 1:1
Enter element 2:1
Enter element 3:0
Enter element 4:1
Enter element 5:0
Enter element 6:0
Enter element 7:1
Enter element 8:1
Enter element 9:1
Enter element 10:0
Sorted Array
0 0 0 0 1 1 1 1 1 1 

Time Complexity: O(n)

As this approach involves simple iteration through the array, the time complexity remains O(n).