# Program for Sorting of elements by frequency in C++

## Sorting of elements by frequency in C++

Here, in this page we will discuss the program for sorting of elements by frequency frequency in C++ programming language. We are given with an integer array and need to sort the array on the basis of there occurence. ## Method Discussed :

• Method 1 : Naive Approach
• Method 2 : Using Hash-map and then sorting.

Let’s discuss both methods one by one in brief.

## Method 1 :

• First we declare an array.
• Declare two 2d array arr[MAX] and brr[MAX].
• Store 1d array in 0th index of arr array.
• Set arr[] = 0for all indexes upto n.
• Now, count the frequency of elements of the array.
• If element is unique the push it at brr[] array, and its frequency will represent by brr[].
• Now, sort the brr on the basis of frequency.
• Print the brr array on basis of their frequency.

### Method 1 : Code in C

Run
```#include <bits/stdc++.h>
using namespace std;
#define MAX 256
int main ()
{
int a[]={10, 20, 10, 10, 20, 30, 30, 30, 30, 0};
int n = sizeof(a)/sizeof(a);
int arr[MAX], brr[MAX];
int k = 0, temp, count;

for (int i = 0; i < n; i++){
arr[i] = a[i];
arr[i] = 0;
}

// Unique elements and its frequency are stored in another array
for (int i = 0; i < n; i++){
if (arr[i])
continue;
count = 1;
for (int j = i + 1; j < n; j++){
if (arr[i] == arr[j]){
arr[j] = 1;
count++;
}
}
brr[k] = arr[i];
brr[k] = count;
k++;
}
n = k;

//Store the array and its frequency in sorted form
for (int i = 0; i < n - 1; i++)
{
temp = brr[i];
for (int j = i + 1; j < n; j++)
{
if (temp < brr[j])
{
temp = brr[j];
brr[j] = brr[i];
brr[i] = temp;

temp = brr[j];
brr[j] = brr[i];
brr[i] = temp;
}
}
}
for (int i = 0; i < n; i++)
{
while (brr[i] != 0)
{
cout<< brr[i] <<" ";
brr[i]--;
}
}
return 0;
}```

### Output

`30 30 30 30 10 10 10 20 20 0`

## Method 2 :

In this method we will use the concept of hashing. We first declare the hash map and insert all the elements in the map, in which key represents the array elements and value represents the count of their occurrence.

### Method 2 : Code in C++

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

// Compare function
bool compare(pair<int, pair<int, int> > p,pair<int, pair<int, int> > p1)
{
if (p.second.second != p1.second.second)
return (p.second.second > p1.second.second);
else
return (p.second.first < p1.second.first);
}
void sortByFrequency(int arr[], int n)
{
unordered_map<int, pair<int, int> > mp;
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);
}
auto it = mp.begin();

vector<pair<int, pair<int, int> > > b;
for (it; it != mp.end(); ++it)
b.push_back(make_pair(it->first, it->second));

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

for (int i = 0; i < b.size(); i++) {
int count = b[i].second.second;
while (count--)
cout << b[i].first << " ";
}
}

// Driver Function
int main()
{
int arr[] = {10, 20, 10, 10, 20, 30, 30, 30, 30, 0};
int n = sizeof(arr) / sizeof(arr);

sortByFrequency(arr, n);

return 0;
}```

### Output

`30 30 30 30 10 10 10 20 20 0`