## Given an array, Sort the array according to the frequency of the elements

### Example

**INPUT:**

arr[] = {1,1,3,3,3,6,6,6,6}

**OUTPUT:**

{6,6,6,6,3,3,3,1,1}

**Time Complexity: O(nlogn)**

In this method the main idea is to insert the elements in BST one by one and if the element is already present then increment the count of the node. Sort the elements using count value of each element.

Each node in BST contains element, count. ie, element is to store the value, count to store the frequency

### Algorithm

**1.** Create a BST and while creating a BST maintain the count ie, frequency of each element. This step takes O(nlogn)

**2.** Do inorder traversal of BST and store every element and count of each element in an auxiliary array named count[]. Every element in count[] is the element and frequency pair. This step takes O(n) time.

**3.** sort count[] according to frequency of the elements. This step takes O(nlogn)

**4.** Traverse the sorted count[] array, For each element in count[] array print freq times. ie, if the element is 3 and freq is 2 then print 2, 2.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
/* A BST node has data, freq, left and right pointers */
struct BSTNode
{
struct BSTNode *left;
int data;
int freq;
struct BSTNode *right;
};
// A structure to store data and its frequency
struct dataFreq
{
int data;
int freq;
};
// compare func to sort the array according to decreasing order of frequency //
int compare(const void *a, const void *b)
{
return ( (*(const dataFreq*)b).freq - (*(const dataFreq*)a).freq );
}
/* Helper function that allocates a new node with the given data,
frequency as 1 and NULL left and right pointers.*/
BSTNode* newNode(int data)
{
struct BSTNode* node = new BSTNode;
node->data = data;
node->left = NULL;
node->right = NULL;
node->freq = 1;
return (node);
}
// A utility function to insert a given key to BST. If element
// is already present, then increases frequency
BSTNode *insert(BSTNode *root, int data)
{
if (root == NULL)
return newNode(data);
if (data == root->data) // If already present
root->freq += 1;
else if (data < root->data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return root;
}
// Function to copy elements and their frequencies to count[].
void store(BSTNode *root, dataFreq count[], int *index)
{
// Base Case
if (root == NULL) return;
// Recur for left substree
store(root->left, count, index);
// Store item from root and increment index
count[(*index)].freq = root->freq;
count[(*index)].data = root->data;
(*index)++;
// Recur for right subtree
store(root->right, count, index);
}
// The main function that takes an input array as an argument
// and sorts the array items according to frequency
void sortByFrequency(int arr[], int n)
{
// Create an empty BST and insert all array items in BST
struct BSTNode *root = NULL;
for (int i = 0; i < n; ++i)
root = insert(root, arr[i]);
// Create an auxiliary array 'count[]' to store data and
// frequency pairs. The maximum size of this array would
// be n when all elements are different
dataFreq count[n];
int index = 0;
store(root, count, &index);
// Sort the count[] array according to frequency (or count)
qsort(count, index, sizeof(count[0]), compare);
// Finally, traverse the sorted count[] array and copy the
// i'th item 'freq' times to original array 'arr[]'
int j = 0;
for (int i = 0; i < index; i++)
{
for (int freq = count[i].freq; freq > 0; freq--)
arr[j++] = count[i].data;
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {1,1,3,3,3,6,6,6,6};
int n = sizeof(arr)/sizeof(arr[0]);
sortByFrequency(arr, n);
printArray(arr, n);
return 0;
}
```