Sort elements by frequency C++ program
By Meetali TomerIn 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