Sort by count of set bits

Given an array of integers, sort the array (in descending order) according to count of set bits in a binary representation of array elements. 

Note: For integers having the same number of set bits in their binary representation, sort according to their position in the original array i.e., a stable sort.

 

Example 1:

Input: 
arr[] = {5, 2, 3, 9, 4, 6, 7, 15, 32};
Output:
15 7 5 3 9 6 2 4 32
Explanation:
The integers in their binary
representation are:
15 - 1111
7  - 0111
5  - 0101
3  - 0011
9  - 1001
6  - 0110
2  - 0010
4  - 0100
32 - 10000
hence the non-increasing sorted order is:
{15}, {7}, {5, 3, 9, 6}, {2, 4, 32}

 

Example 2:

Input: 
arr[] = {1, 2, 3, 4, 5, 6};
Output: 
3 5 6 1 2 4
Explanation:
3  - 0110
5  - 0101
6  - 0110
1  - 0001
2  - 0010
4  - 0100
hence the non-increasing sorted order is
{3, 5, 6}, {1, 2, 4}

method 1:

step 1: we have to traverse through an  array and select each element and count the number of set bits

step 2: Count the number of set bit, ie. we are finding no of ones present in a binary representation of the particular number in the array, we are doing this in the function setbitcount 

step 3: take a vector and create pairs of array elements and count of set bits

step 4: sort the array based on the count of set bit in descending order 

why stable_sort instead of sort()? 
Sometimes we want to make sure that the order of equal elements is the same in the sorted array as it was in the original array. This can be useful if these values have associated other fields. For example, consider sorting students by marks, if two people have the same marks, we may want to keep them in the same order as they appear input.

bool cmp(pair<int,int> p, pair<int,int> q)
{ 
    return (p.second > q.second); 
} 

int setbitcount(int num)
{
   int count = 0;
    
    while ( num ) 
    {   
        if ( num % 2)
        count++;
        num =num/2;
    }
    
    return count;
}
    
    
void sortBySetBitCount(int a[], int n)
{    
      vector<pair<int, int> > b;
     for(int i=0;i<n;i++)
     {
       int x=setBitCount(a[i]);  
       b.push_back(make_pair(a[i],x));
       
     }
       stable_sort(b.begin(), b.end(), cmp); 
       int x=0;

     for(auto i:b)
     {
         a[x]= i.first;
         x++;
     }
    return a;
}

time complexity:O(nlogn)

space complexity:O(n)

method 2:  

step 1: we will use inbuild function __builtin_popcount() to find the count of set bits 

step 2: sort based on count of set bits

bool cmp(int a,int b)
{
return __builtin_popcount(a)> __builtin_popcount(b);
}

void sortBySetBitCount(int arr[], int n)
{
stable_sort(arr,arr+n,cmp);
}

time complexity:O(nlogn)

space complexity:O(1)