Sort Elements by Frequency

Introduction

Sorting elements by frequency is a perfect problem to learn problem-solving using Sorting and a single scan. Such problems are popular where we need to rearrange the input in place to get the output.

In this blog, we will learn how to sort elements by frequency along with their time complexity and space complexity.

Problem Statement

Given an array of index n, the problem is to sort the array based on its frequency, which means the element having the higher frequency will come first, and the element with the low frequency will come last.

Sample Example

Approach

1. The first step of this approach is to declare an array.
2. Now, declare two more arrays having the name arr[MAX][2] and brr[MAX][2].
3. Then, store the 1d array in the 0th index of the given arr array. 
4. Set value for arr[][1] = 0 for all indexes up to the size of array n.
5. Count the frequency of elements in the array.
6. Now, if the element is unique, push it in the array brr[][0], and its frequency will be represented by brr[][1].
7. Sort the brr array on the basis of its frequency.
8. Then print the brr array.

Implementation

#include<stdio.h>
#define MAX 256
int main ()
{
     int a[]={2, 3, 42, 1, 3, 3, 5, 8, 5, 2};
     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)
            {
                 printf (" %d ", brr[i][0]);
                 brr[i][1]--;
            }
      }
return 0;
}

You can also try this code with Online C Compiler

Run Code

OUTPUT

Time complexity

The time complexity of the given problem, "Sort elements by frequency," is O(n^2).

Space complexity

The time complexity of the given problem, "Sort elements by frequency," is O(1).

Also see,  Rabin Karp Algorithm

Refer to know about :  Topological sort