Sorting of elements by frequency

C++ Program to sort the elements of array on the basis of frequency

 

Here in this program, we will discuss the sorting of the  elements by frequency in a given array. You need to print the elements of an array in the descending order of their frequency and if the numbers have same frequency then print the one which comes first.

Example of Sorting of elements by frequency : Let’s the given A[ ] = {2, 3, 2, 5, 6, 2, 3, 9, 5, 6}

After sorting the array will become A[ ] = {2, 2, 2, 3, 3, 5, 5, 6, 6, 9}.

Sorting element in array by frequency using C++

Keypoint

In this section we will learn about basic knowledge which we need to know before coding the above Program. So we must have knowledge of what is an array? 

What is an array?
An array is a data structure, it is collection of similar data elements which is stored at contiguous memory locations in which each data element can be accessed directly by only using its index number.

Algorithm:

  • To sort the array according to there frequency , we will store the values in the hash map .
  • In map key will track the elements and frequency will store as values.
  • After traverse over the entire array, the map will contains the element of array along with their frequency.
  • Finally, we will sort the map according to the count.

 

C++ Program based on Sorting of elements by frequency algorithm :

#include <bits/stdc++.h>
using namespace std;


// Compare function
bool
compare (pair < int, pair < int, int > >a, pair < int, pair < int, int > >b)
{

if (a.second.second != b.second.second)
return (a.second.second > b.second.second);

else
return (a.second.first < b.second.first);

}

void
sortByFrequency (int arr[], int n)
{
unordered_map < int, pair < int, int >>mp; // hash map

for (int i = 0; i < n; i++)
{
if (mp.find (arr[i]) != mp.end ())
mp[arr[i]].second++;

else
mp[arr[i]] = make_pair (i, 1);

}
// store the count of all the elements in the hashmap
// Iterator to Traverse the Hashmap

auto it = mp.begin ();

// Vector to store the Final Sortted order
vector < pair < int, pair < int, int >>>p;

for (it; it != hash.end (); ++it)
p.push_back (make_pair (it->first, it->second));

sort (p.begin (), p.end (), compare);

// Printing the sorted array by frequency
cout << "\nSorted Array: ";

for (int i = 0; i < p.size (); i++)
{
int count = p[i].second.second;

while (count--)
cout << p[i].first << " ";
}
}

// Driver Function
int
main ()
{
int n; // declare a variable to store the size of array

cout << "Enter the size of array: ";
cin >> n;

int arr[n]; //deaclare an array arr of size n

cout << "\n Enter the elements: ";

for (int i = 0; i < n; i++)
cin >> arr[i];

sort_by_freq (arr, n); //calling the sort_by_freq

return 0;

}
Enter the size of array : 7
Enter the elements: 3 2 1 2 3 1 3

Sorted Array : 3 3 3 2 2 1 1