## Question Name:Sorting Elements of an Array by Frequency

```#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```