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 Approach to Sort an Array of 0s and 1s

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 Approach to Sort an Array of 0s and 1s

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 Concatenate Two Character Arrays.
  2. Program to Check whether given String is Palindrome or not.
  3. Program to convert lower-case alphabet to upper-case alphabet and vice-versa.
  4. Program to count total number of words in a string.
  5. Program to find smallest and largest word of the String.
  6. Program to find Most Frequent Character of the String.
  7. Program to Remove all the blank spaces from the String.
  8. Program to check if String is isogram or not.
  9. Program to Reverse Each word of the String.
  10. Program to Print All the Substring of the Given String.
  11. Program to find longest palindromic Substring.
  12. Detect a Loop in a Linked List.
  13. Find the Length of the Loop present in the Linked List.
  14. Detect and Remove Loop from a Linked List.
  15. Segregate Even and Odd Nodes in a Linked List.
  16. Delete Complete Linked List.
  17. Delete Nth Node of the Linked List.
  18. Delete without head pointer of the Linked List.
  19. Delete All Occurrences of particular node of the Linked List.
  20. Delete Alternate Nodes of the Linked List.

You may also like...

Leave a Reply

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