Sort an array containing elements of two types
Sep 02, 2023 pm 02:21 PMThere 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 ofExample
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 ofExample
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 ofExample
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 ofExample
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!

Hot Article

Hot tools Tags

Hot Article

Hot Article Tags

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

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

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

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

Application of PHP array grouping function in data sorting

Best Practices for Deep Copying PHP Arrays: Discover Efficient Methods

Advanced sorting of PHP arrays: custom comparators and anonymous functions

The role of PHP array grouping function in finding duplicate elements
