Sort elements by frequency of occurrences

Sort array elements in such a way that the element with the highest number of occurences comes first. If the number of occurences are equal then the print the number which appeared first in the array.

Input:  arr[] = {2, 5, 2, 8, 5, 6, 8, 8}

Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}

Method1

TIME COMPLEXITY: O(NlogN)

SPACE COMPLEXITY: O(N)

The question involves two prime problems

  • Sorting via frequency and
  • Maintaining order for resolving clash.

We make use of two advanced and powerful data structures namely :

MAP  and  MULTIPMAP.

Map has the property of mapping some key to the value.

Multimap does the same function but in addition to maps it maintains the key in sorted fashion and specific order.Exactly the function we require.

Algorithm

1. Add the elements in the map ( map<int,int> ).
a. If they are not present then add them and make the count 1.
b. Else increment the count of the value by 1 as it occurred again.
Map makes <value,frequency> pairs.

2. Now traverse the map and keep adding the elements into multimap in this way :
a. Make the 2nd field of map i.e the frequency of the map , as the key of multimap so that we get it automatically sorted.
b. Map the first value to the second so each entry in multimap holds <frequency,value> in ascending order on frequency.

3. Now simply traverse the multimap in reverse order to get the desired output.

Program for Algorithm

#include <bits/stdc++.h>
using namespace std;
typedef multimap<int, int> MapType;

int main()
{
    int a[] = {5,8,3,8,5,5,8,3,2,3,5,3};
		int N = sizeof(a)/sizeof(a[0]);
	
    map<int,int> mp; //Map uses the first id as the array element and second as the count of occurences of the element
    
    for(int i=0;i<N;i++)
    {
        if(mp.find(a[i])!=mp.end()) //if the array element is present then just increase the count of occurence of it by 1
            mp[a[i]]++;
        else
            mp[a[i]]=1; //if the array element is not present in the map already then add it
    }
    
		multimap<int,int> mp2; // it maintains specific order and count  and while inserting makes it sorted
    
    map<int,int>::iterator it;
    for(it=mp.begin();it!=mp.end();it++)
      mp2.insert(MapType::value_type(it->second,it->first)); //Second becomes the key as we need to sort according to frequency.
      
	  map<int,int>::reverse_iterator itr;
    for(itr=mp2.rbegin();itr!=mp2.rend();itr++)
    {
    	//Reverse the multimap and print so that it prints in decreasing order.
        for(int i=0;i<itr->first;i++)
            cout<<itr->second<<"\t";
    }
    
    return 0;
}
Try It




Next > < Prev
Scroll to Top