#include <iostream> 
#include <stdlib.h> 
using namespace std; 
  
struct BSTNode 
{ 
    struct BSTNode *left; 
    int data; 
    int freq; 
    struct BSTNode *right; 
}; 
  
struct dataFreq 
{ 
    int data; 
    int freq; 
}; 
  

int compare(const void *a, const void *b) 
{ 
    return ( (*(const dataFreq*)b).freq - (*(const dataFreq*)a).freq ); 
} 
  
BSTNode* newNode(int data) 
{ 
    struct BSTNode* node = new BSTNode; 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
    node->freq = 1; 
    return (node); 
} 
  

BSTNode *insert(BSTNode *root, int data) 
{ 
    if (root == NULL) 
        return newNode(data); 
    if (data == root->data)  
        root->freq += 1; 
    else if (data < root->data) 
        root->left = insert(root->left, data); 
    else
        root->right = insert(root->right, data); 
    return root; 
} 
  
void store(BSTNode *root, dataFreq count[], int *index) 
{ 
    if (root == NULL) return; 
  
    store(root->left, count, index); 
  
    count[(*index)].freq = root->freq; 
    count[(*index)].data = root->data; 
    (*index)++; 
  
    store(root->right, count, index); 
} 
  
void sortByFrequency(int arr[], int n) 
{ 
    struct BSTNode *root = NULL; 
    for (int i = 0; i < n; ++i) 
        root = insert(root, arr[i]); 
  
  
    dataFreq count[n]; 
    int index = 0; 
    store(root, count, &index); 
  
    qsort(count, index, sizeof(count[0]), compare); 
  
   
    int j = 0; 
    for (int i = 0; i < index; i++) 
    { 
        for (int freq = count[i].freq; freq > 0; freq--) 
            arr[j++] = count[i].data; 
    } 
} 
  
void printArray(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
    cout << endl; 
} 
  
/* Driver program to test above functions */
int main() 
{ 
 
      int n,k,j,i;
  cin>>k;
 
    for(j=0;j<k;j++) 
  { cin>>n;
  int arr[n];
  for(i=0;i<n;i++) 
  { 
    cin>>arr[i];
  } 
    sortByFrequency(arr, n); 
    printArray(arr, n); }
    return 0; 
}  

Problem Description

Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.

If frequencies of two elements are same, print them in increasing order.

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 integers A1, A2, …, AN denoting the elements of the array.

Output:

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

Constraints:

1 <= T <= 70
30 <= N <= 130
1 <= A [ i ] <= 60

• Test Case 1

  Input (stdin)

  1
  5
  5 4 5 4 6
  

  Expected Output

  4 4 5 5 6

• Test Case 2

  Input (stdin)

  2
  6
  1 2 3 2 1 5
  8
  2 22 3 6 55 22 1 3
  

  Expected Output

  1 1 2 2 3 5 
  3 3 22 22 1 2 6 55