Sort elements by frequency | Sorting elements of an array by frequency

Program to sort elements by frequency in a given array is discussed here. You need to print the elements of an array in the decreasing frequency and if 2 numbers have same frequency then print the one which came first.

sort elements by frequency

Program to Sort elements by frequency

//Sort elements by frequency using sorting

#include<bits/stdc++.h>
using namespace std;
// struct to sort
struct ele
{
int count, index, val;
};
//sort with the values
bool comp1(struct ele a, struct ele b) {
return (a.val < b.val);
}
//sort by no of times or order
bool comp2(struct ele a, struct ele b) {
if (a.count != b.count) return (a.count < b.count);
else return a.index > b.index;
}
void freqSort(int arr[], int n)
{
struct ele element[n];
for (int i = 0; i < n; i++)
{
       element[i].index = i;
       element[i].count = 0;
       element[i].val = arr[i]; }
/* maintain the same order */
   stable_sort(element, element+n, comp1);
/* initialize count of first element as 1 */
   element[0].count = 1;
/* how many times other elements appear*/
for (int i = 1; i < n; i++)
{
    if (element[i].val == element[i-1].val)
    {
           element[i].count += element[i-1].count+1;
       /* set previous as -1 to sort again*/
           element[i-1].count = -1;
           /* first index is maintained*/
           element[i].index = element[i-1].index;
    }
    /* if previous element != curr
         count=1 */
    else element[i].count = 1;
}
  /* sort with the help of count and order */
   stable_sort(element, element+n, comp2);
for (int i = n-1, index=0; i >= 0; i–)
    if (element[i].count != -1)
          for (int j=0; j<element[i].count; j++)
               arr[index++] = element[i].val;
}
// main
int main()
{
int t;
   cin>>t;
 for(int j=0;j<t;j++){
int n;
   cin>> n;
int arr[n];
for (int i=0; i<n; i++)
      cin>> arr[i];
   freqSort(arr, n);
for (int i=0; i<n; i++)
   cout << arr[i] << ” “;
 }
return 0;
}

// Sort elements by frequency using hashing

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

unordered_map<int, int> m2;

bool sort_by_value(const pair<int, int>& a, const pair<int, int>& b)
{
if (a.second == b.second)
return m2[a.first] < m2[b.first];

return a.second > b.second;
}

void sort_by_frequency(int a[], int n)
{
unordered_map<int, int> m;
vector<pair<int, int> > v;

for (int i = 0; i < n; ++i) {

m[a[i]]++;

if (m2[a[i]] == 0)
m2[a[i]] = i + 1;
}

copy(m.begin(), m.end(), back_inserter(v));

sort(v.begin(), v.end(), sort_by_value);

for (int i = 0; i < v.size(); ++i)
for (int j = 0; j < v[i].second; ++j)
cout << v[i].first << ” “;
}

int main()
{
int n;
cout << “\nEnter the number of elements : “;
cin >> n;
int a[n];
cout << “\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}

sort_by_frequency(a, n);

return 0;
}

Sort elements by frequency using BST

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

struct BSTNode
{
struct BSTNode *left;
int data;
int freq;
struct BSTNode *right;
};

struct dataFreq
{
int data;
int freq;
};

int compare(const void *a, const void *b)
{
return ( (*(const dataFreq*)b).freq – (*(const dataFreq*)a).freq );
}

BSTNode* newNode(int data)
{
struct BSTNode* node = new BSTNode;
node->data = data;
node->left = NULL;
node->right = NULL;
node->freq = 1;
return (node);
}

BSTNode *insert(BSTNode *root, int data)
{
if (root == NULL)
return newNode(data);
if (data == root->data)
root->freq += 1;
else if (data < root->data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return root;
}

void store(BSTNode *root, dataFreq count[], int *index)
{
if (root == NULL) return;

store(root->left, count, index);

count[(*index)].freq = root->freq;
count[(*index)].data = root->data;
(*index)++;

store(root->right, count, index);
}

void sort_by_frequency(int arr[], int n)
{
struct BSTNode *root = NULL;
for (int i = 0; i < n; ++i)
root = insert(root, arr[i]);

dataFreq count[n];
int index = 0;
store(root, count, &index);

qsort(count, index, sizeof(count[0]), compare);

int j = 0;
for (int i = 0; i < index; i++)
{
for (int freq = count[i].freq; freq > 0; freq–)
arr[j++] = count[i].data;
}
}

void display_elements(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << ” “;
cout << endl;
}

int main()
{
int n;
cout << “\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout << “\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort_by_frequency(arr, n);
display_elements(arr, n);
return 0;
}

Complexity of sorting elements of an array based on their frequencies: n(logn)

Input:                  
1
5
5 5 4 6 4

Output:
5 5 4 4 6

Input:
1
5
5 3 4 5 4

Output:
5 5 4 4 3