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.
Sort Elements by Frequency of Occurrences in C++
To solve sort elements by frequency of occurrences in C we can use an array to count the occurrences of each element , and then use a sorting algorithm to sort the elements by their counts . Lets see this in detail .
Method Discussed :
- Method 1 : Naive Approach
- Method 2 : Using Hash-map and then sorting.
Method 1 :
- First we declare an array.
- Declare two 2d array arr[MAX][2] and brr[MAX][2].
- Store 1d array in 0th index of arr array.
- Set arr[][1] = 0for all indexes upto n.
- Now, count the frequency of elements of the array.
- If element is unique the push it at brr[][0] array, and its frequency will represent by brr[][1].
- Now, sort the brr on the basis of frequency.
- Print the brr array on basis of their frequency.
Method 1 :
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[0]);
int arr[MAX][2], brr[MAX][2];
int k = 0, temp, count;
for (int i = 0; i < n; i++){
arr[i][0] = a[i];
arr[i][1] = 0;
}
// Unique elements and its frequency are stored in another array
for (int i = 0; i < n; i++){
if (arr[i][1])
continue;
count = 1;
for (int j = i + 1; j < n; j++){
if (arr[i][0] == arr[j][0]){
arr[j][1] = 1;
count++;
}
}
brr[k][0] = arr[i][0];
brr[k][1] = count;
k++;
}
n = k;
//Store the array and its frequency in sorted form
for (int i = 0; i < n - 1; i++)
{
temp = brr[i][1];
for (int j = i + 1; j < n; j++)
{
if (temp < brr[j][1])
{
temp = brr[j][1];
brr[j][1] = brr[i][1];
brr[i][1] = temp;
temp = brr[j][0];
brr[j][0] = brr[i][0];
brr[i][0] = temp;
}
}
}
for (int i = 0; i < n; i++)
{
while (brr[i][1] != 0)
{
cout<< brr[i][0] <<" ";
brr[i][1]--;
}
}
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.
Pair in C++ STL
Pair is used to combine together two values that may be different in type.
The first element is referenced as ‘first’ and the second element as ‘second’ and the order is fixed (first, second).
To access the elements, we use variable name followed by dot operator followed by the keyword first or second.
The first element is referenced as ‘first’ and the second element as ‘second’ and the order is fixed (first, second).
To access the elements, we use variable name followed by dot operator followed by the keyword first or second.
Method 2 :
#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[0]);
sortByFrequency(arr, n);
return 0;
}
Output
30 30 30 30 10 10 10 20 20 0
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Arrays
- Introduction to Arrays – C | C++ | Java
- Introduction to 2-D Arrays – C | C++ | Java
- Sorting of Array – C | C++ | Java
- Array Rotation – C | C++ | Java
- Reverse an array or string- C | C++ | Java
- Find pairs in array with given sum – C | C++ | Java
- Sort the array in Waveform – C | C++ | Java
- Majority Element in Array – C | C++ | Java
- Boyer-Moore’s Voting Algorithm – C | C++ | Java
- K-pairs with smallest sum in 2 arrays – C | C++ | Java
- Largest Sum Contigous SubArray – C | C++ | Java
- Maximum Average Sub-array of K length – C | C++ | Java
- Size of sub-array with max sum – C | C++ | Java
- Sub-array with given sum – C | C++ | Java
- Triplet that sum to a given value – C | C++ | Java
- Segregate 0’s and 1’s in array – C | C++ | Java
- Segregate 0’s 1’s and 2’s in array – C | C++ | Java
- Sort elements in array by frequency – C | C++ | Java
- Finding pythagorean triplets in an array – C | C++ | Java
- Reorder array using given indexes – C | C++ | Java
- Merging two sorted arrays – C | C++ | Java
- Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
- Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java
Login/Signup to comment