Sort an Array of 0s and 1s

Sort an Array of 0s and 1s” is one of the favorite technical interview problem of array data structure. Here, we are given an array of size ‘n’ and our task is to sort this array. 

Array contains only 0s and 1s.

Example:

INPUT:
Arr[5] = {1, 0, 1, 0, 1}
OUTPUT:
Arr[5] = {0, 0, 1, 1, 1}

There are many methods to sort an array of 0s and 1s. Some of them are:

METHOD 1: Brute-force

The brute-force solution of the given problem is to simply sort the array using quick sort or merge sort.

The time complexity of the above problem would be O(nlogn) for sorting.

METHOD 2: Count and Replace

This method is more time efficient and requires O(n) time complexity with traversing the array two times only.

In this method, we count the occurrence of 0s as count, and then, we put 0s at the beginning and rest 1s in the array.

C++ Program to sort an array of 0s and 1s is as follows:

/* Program to sort an array of 0s and 1s */  
#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    /* Scan array size */  
    int n;  
    cout<<"Enter array size:";  
    cin>>n;  
      
    /* Scan array elements */  
    int arr[n];  
    cout<<"\nEnter array elements:\n";  
    for(int i = 0; i < n; i++)  
    cin>>arr[i];  
      
    /* Count 0s  */  
    int count0 = 0;  
    for(int i = 0; i < n; i++)  
    {  
        if(arr[i] == 0)  
        count0++;  
    }  
      
    /* we put 0s at the beginning and rest 1s in the array */  
    for(int i = 0; i < count0; i++)  
    {  
        arr[i] = 0;  
    }  
    for(int i = count0; i < n; i++)  
    {  
        arr[i] = 1;  
    }  
      
    /* Print the resultant array */  
    cout<<"\nThe sorted array is:\n";  
    for(int i = 0; i < n; i++)  
    cout<<arr[i]<<" ";  
}  
OUTPUT:
Enter array size: 5
Enter array elements:
0 1 0 1 0
The sorted array is:
0 0 0 1 1
 
Time Complexity: 
This requires two times traversal of the array.
O(n), where n is the size of the array

METHOD 3: Two Pointers

The steps required to sort an array of 0s and 1s are as follows:

  1. Scan array size.
  2. Scan array elements.
  3. Set ptr1 = 0 and ptr2 = n-1
  4. While(ptr1 < ptr2)
  5. while(arr[ptr1] == 0) then ptr1++.
  6. while(arr[ptr2] == 1) then ptr2–.
  7. If(ptr1 < ptr2) then swap(arr[ptr1],arr[ptr2]) and  ptr1++ ,ptr2–.

C++ Program to sort an array of 0s and 1s is as follows:

/* Program to sort an array of 0s and 1s */  
#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    /* Scan array size */  
    int n;  
    cout<<"Enter array size:";  
    cin>>n;  
      
    /* Scan array elements */  
    int arr[n];  
    cout<<"\nEnter array elements:\n";  
    for(int i = 0; i < n; i++)  
    cin>>arr[i];  
      
    /* Initiate pointers */  
    int ptr1 = 0, ptr2 = n-1;  
    while(ptr1 < ptr2)  
    {  
        /* Increment ptr1 till we get 0s */  
        while(arr[ptr1] == 0)  
        ptr1++;  
          
        /* Decrement ptr2 till we get 1s */  
        while(arr[ptr2] == 1)  
        ptr2--;  
          
        /* swap elements */  
        int temp = arr[ptr1];  
        arr[ptr1] = arr[ptr2];  
        arr[ptr2] = temp;  
        ptr1++;  
        ptr2--;  
    }  
      
    /* Print the resultant array */  
    cout<<"\nThe sorted array is:\n";  
    for(int i = 0; i < n; i++)  
    cout<<arr[i]<<" ";  
}  

OUTPUT:
Enter array size: 5
Enter array elements:
0 1 0 1 0
The sorted array is:
0 0 0 1 1
 
Time Complexity:
This method requires only one time traversal of array
O(n), where n is the size of the array.

Related Posts:

  1. Program to merge two sorted arrays.
  2. Program to find missing number in an array.
  3. Program to sort if array is sorted.
  4. Program to print Alternate Elements of an Array.
  5. Program to swap kth element from beginning to kth element from end in an Array.
  6. Program to print all possible subarrays of the given array.
  7. Program to print kth smallest and kth largest element of an Array.
  8. Program to find equilibrium index of an Array.
  9. Program to find majority element of an Array.
  10. Program to find mean of the Array.
  11. Program to Reverse an Array.
  12. Program to count number of odd numbers and even numbers in an array.
  13. Program to find absolute difference between sum of odd index elements and even index elements.
  14. Program to find smallest and largest element of the array.
  15. Program to count occurrences of a particular element in an array.
  16. Program to search an element in an Array (Linear Search).
  17. Program to Rotate Array Elements by ‘D’ positions.
  18. Program to find most frequent element in an array.
  19. Program to find pair in an array with given sum.
  20. Program to find first repeating element of an array.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *