Sort an array containing elements of two types

There are different ways to sort an array containing only two types of elements (i.e. only 1 and 0). We'll discuss three different ways to achieve this goal. The first method simply uses the predefined sort() function to sort the given array. The second method is the counting sort method where we will count the number of 0's and 1's and then update the array by first writing the number of 0's and then the number of 1's. In the last method, we used the double pointer method.

Problem Statement

We are given an array containing only 1 and 0. Our task is to arrange all 0s and 1s so that 1 is on the rightmost side of the array and 0 is on the left side of the array

The Chinese translation of

Example

is:

Example

Given array: a[] = [ 1, 1, 0, 1, 0, 1, 0, 1 ]
Resultant array: a[] = [ 0, 0, 0, 1, 1, 1, 1, 1 ]

Method 1: Brute force cracking method.

In this method, we will sort the array directly using the sort() function. Since 1>0, after sorting, all 1's will be arranged on the right side of the array, and all 0's will be arranged on the left.

Sort() function: Sort() function takes O(NlogN) time and returns the array in ascending order.

The Chinese translation of

Example

is:

Example

The following is a C implementation for sorting an array containing two types of elements.

#include <bits/stdc++.h>
using namespace std;
int main(){
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
   int len = sizeof(a) / sizeof( a[0] );
   
   // sort function to
   // sort the array
   sort( a, a + len);
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0; iterator<len; iterator++){
      cout << a[iterator] <<" ";
   }
   return 0;
}

Output

When compiled, the above program will produce the following output -

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Method 2: Counting sorting method

In this method we will simply count the number of 0's and 1's in the array and then update the array with 0 at the beginning and 1 at the end.

By doing this, we will have all 0's in the leftmost part of the array and all 1's in the rightmost part of the array, which will automatically represent the desired sorted array.

This is a simple method, but it inserts new values ​​into the array instead of just exchanging their positions, so this method is not efficient.

The Chinese translation of

Example

is:

Example

The following is the implementation of the above method using C.

#include <iostream>
using namespace std;
int main() {
   int count = 0 ;
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
   int len = sizeof(a) / sizeof(a[0]);
   for(int iterator=0; iterator<len; iterator++){
      if( a[iterator] == 0 )
      count++;
   }
   for(int iterator=0 ; iterator<len ; iterator++){
      if(count){
         a[iterator] = 0 ;
         count-- ;
      }
      else a[iterator] = 1;
   }
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0 ; iterator<len ; iterator++){
      cout<< a[iterator] << " ";
   }
   return 0;
}

Output

When compiled, it will produce the following output -

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Time complexity - Since we only use one loop, the time complexity of this method is O(N)

Space complexity - O(1). Although we use additional variables, since they are linear, the space complexity is constant.

Method 3: The best way to solve this problem

In this method, we will keep two pointers, start and end. We will simultaneously traverse from the beginning of the array (index 0) using the start pointer and traverse from the end (index len-1) using the end pointer.

Our task is to arrange all the 1's to the far right of the array, which will automatically arrange all the 0's to the left of the array.

We start from the initial index, if the found element is 1, we swap it with the element at index "end" and decrement the end pointer by 1.

If the found element is 0, then there is no need to perform any swap operations, because it is already at the leftmost position, we only need to increase the starting pointer by 1.

The Chinese translation of

Example

is:

Example

The following is the code to implement this method -

#include <bits/stdc++.h>
using namespace std;
int main(){
   int start =0 ;
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 } ;
   int len = sizeof(a) / sizeof( a[0] ) ;
   int end = len-1;
   while(start < end){
      if( a[start] ==1){
         swap(a[start], a[end]);
         end--;
      }
      else
         start++;
   }
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0 ; iterator<len ; iterator++){
      cout<< a[iterator] << " ";
   }
   return 0;
}

Output

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Time Complexity - Since we iterate over the array only once, the time complexity of this method is linear, i.e. O(N)

Space complexity − Since we are not using any extra space, the space complexity is O(1).

in conclusion

In this article, we discussed three different ways to sort an array containing only two types of elements (i.e. only 1 and 0).

The above is the detailed content of Sort an array containing elements of two types. For more information, please follow other related articles on the PHP Chinese website!