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.

Sorting element in array by frequency using C++

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][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 : 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[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.

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[0]);

      sortByFrequency(arr, n);

      return 0;
}

Output

30 30 30 30 10 10 10 20 20 0