# Sort elements by frequency C++ program

In this tutorial, we will learn to sort elements of an array in decreasing order based on the frequency of elements in C++ programming.

If the frequency of any two elements is the same, then sort them in decreasing order based on their value.

**Examples**

- INPUT: [3, 2, 4, 4]

OUTPUT: [4, 4, 2, 3 ] *2 and 3 have the same frequency *

- INPUT: [1 , 2 , 3 , 2 , 1 , 2 , 1]

OUTPUT: [1 , 1 , 1 , 2 , 2 , 2 , 3]

- INPUT: [3 , 2 , 4 , 3 , 2 , 2 , 1 , 1]

OUTPUT: [2 , 2 , 2 , 1 , 1 , 3 , 3 , 4]

### Method-Sorting Using Custom Sort

Use an unordered_map to count how many times each character occurs in the array –the keys are elements and the values are frequencies.

- Traverse each element of the given array.
- Check whether the current element is present in unordered_map or not.
- If it is present, then update the frequency of the current element by 1 i.e m[array[i]]++
- Else insert the characters with frequency 1 i.e. m[array[i]]=1

Then sort the array using the custom sort function by passing an additional comparator function to the sort function.

**Comparator function**

(arg1, arg2)–takes two arguments

return true if arg1 is to be placed before arg2.

Here in this example, we use a lambda function (inline function) as a comparator function.

Syntax –[capture] (arg1 , arg2)

**Capture** is used to capture variables which are within the scope.

Here we capture the unordered_map m by reference.

Below is given our C++ code:

#include<bits/stdc++.h> using namespace std; int main(){ vector<int> array{3 , 2 , 4 , 3 , 2 , 2 , 1 , 1}; unordered_map<int , int>m; for(int i=0;i<array.size();i++){ if(m.find(array[i])==m.end()) m[array[i]]=1; else m[array[i]]++; } sort(array.begin() , array.end() , [&m](int a , int b){ if(m[a]!=m[b]) return m[a]>m[b]; return a<b; }); for(int i=0;i<array.size();i++) cout<<array[i]<<" "; return 0; }

OUTPUT

*2 2 2 1 1 3 3 4 *

**Time Complexity -O(n log(n))**

If there are n elements in the array.

Putting the characters into the unordered_map has a cost of O(n) because each of the n characters must be put in, and putting each in is an O(1) operation.

Custom sort function takes n log(n) time if the array contains n elements.

You may also read:

## Leave a Reply