Table of Contents
Problem Statement
Example
Method 1: Brute force cracking method.
Output
Method 2: Counting sorting method
Method 3: The best way to solve this problem
in conclusion
Home Backend Development C++ Sort an array containing elements of two types

Sort an array containing elements of two types

Sep 02, 2023 pm 02:21 PM
array element sort

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 ]
Copy after login

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;
}
Copy after login

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
Copy after login
Copy after login
Copy after login

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;
}
Copy after login

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
Copy after login
Copy after login
Copy after login

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;
}
Copy after login

Output

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1
Copy after login
Copy after login
Copy after login

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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

How to remove duplicate elements from PHP array using foreach loop? How to remove duplicate elements from PHP array using foreach loop? Apr 27, 2024 am 11:33 AM

How to remove duplicate elements from PHP array using foreach loop?

PHP array key value flipping: Comparative performance analysis of different methods PHP array key value flipping: Comparative performance analysis of different methods May 03, 2024 pm 09:03 PM

PHP array key value flipping: Comparative performance analysis of different methods

PHP array multi-dimensional sorting practice: from simple to complex scenarios PHP array multi-dimensional sorting practice: from simple to complex scenarios Apr 29, 2024 pm 09:12 PM

PHP array multi-dimensional sorting practice: from simple to complex scenarios

The Art of PHP Array Deep Copy: Using Different Methods to Achieve a Perfect Copy The Art of PHP Array Deep Copy: Using Different Methods to Achieve a Perfect Copy May 01, 2024 pm 12:30 PM

The Art of PHP Array Deep Copy: Using Different Methods to Achieve a Perfect Copy

Application of PHP array grouping function in data sorting Application of PHP array grouping function in data sorting May 04, 2024 pm 01:03 PM

Application of PHP array grouping function in data sorting

Best Practices for Deep Copying PHP Arrays: Discover Efficient Methods Best Practices for Deep Copying PHP Arrays: Discover Efficient Methods Apr 30, 2024 pm 03:42 PM

Best Practices for Deep Copying PHP Arrays: Discover Efficient Methods

Advanced sorting of PHP arrays: custom comparators and anonymous functions Advanced sorting of PHP arrays: custom comparators and anonymous functions Apr 27, 2024 am 11:09 AM

Advanced sorting of PHP arrays: custom comparators and anonymous functions

The role of PHP array grouping function in finding duplicate elements The role of PHP array grouping function in finding duplicate elements May 05, 2024 am 09:21 AM

The role of PHP array grouping function in finding duplicate elements

See all articles