#include <iostream>

using namespace std; 
  

int countBits(int a) 
{ 
    int count = 0; 
    while (a) 
    { 
        if (a & 1 ) 
            count+= 1; 
        a = a>>1; 
    } 
    return count; 
} 
  

void insertionSort(int arr[],int aux[], int n) 
{ 
    for (int i = 1; i < n; i++) 
    { 
        // use 2 keys because we need to sort both 
        // arrays simultaneously 
        int key1 = aux[i]; 
        int key2 = arr[i]; 
        int j = i-1; 
  
     
        while (j >= 0 && aux[j] < key1) 
        { 
            aux[j+1] = aux[j]; 
            arr[j+1] = arr[j]; 
            j = j-1; 
        } 
        aux[j+1] = key1; 
        arr[j+1] = key2; 
    } 
} 

void sortBySetBitCount(int arr[],int n) 
{ 

    int aux[n]; 
    for (int i=0; i<n; i++) 
        aux[i] = countBits(arr[i]); 
  
    insertionSort(arr, aux, n); 
} 
  
void printArr(int arr[], int n) 
{ 
    for (int i=0; i<n; i++) 
      if(i!=n-1) { 
        cout << arr[i] << " ";} 
  else 
  { 
    cout<<arr[i];}

} 
  
int main() 
{ 
  int k,i,w,j;
  cin>>w;
  for(j=0;j<w;j++) {
  cin>>k;int arr[k];
  for(i=0;i<k;i++) { cin>>arr[i];} 
    sortBySetBitCount(arr, k); 
    printArr(arr, k);
    if(j!=w-1) { cout<<"\n"; } 
  } 
    return 0; 
} 

Problem Description

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

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

For example, if input array is {3, 5}, then output array should also be {3, 5}. Note that both 3 and 5 have same number set bits.

Input: arr[] = {5, 2, 3, 9, 4, 6, 7, 15, 32};
Output: 15 7 5 3 9 6 2 4 32

Input:

The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated array elements.

Output:

Print each sorted array in a seperate line. For each array its numbers should be seperated by space.

Constraints:

1<= T <= 1000
0 <= N <= 100000
1 <= A[i] <= 1000000

• Test Case 1

  Input (stdin)

  2
  3
  3 1 5
  4
  5 16 6 15
  

  Expected Output

  3 5 1
  15 5 6 16

• Test Case 2

  Input (stdin)

  3
  2
  6 5
  5
  15 1 61 24 10
  2
  7 9
  

  Expected Output

  6 5
  61 15 24 10 1
  7 9