Sort Elements by frequency

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


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


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


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);
        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;
    // 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;


Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc


Abhishek was able to crack Microsoft after practicing questions from TutorialCup