Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Implementation
2.1.1.
Time complexity
2.1.2.
Space complexity
3.
Frequently Asked Questions
3.1.
What is the process to reduce the time complexity of the code?
3.2.
What is "Sort elements by frequency"?
3.3.
What is a sorted array in a programming language?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sort Elements by Frequency

Author Sinki Kumari
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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;
}

 

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the process to reduce the time complexity of the code?

We can reduce time complexity by minimal use of loops and by using formulation methods, where giving some formulas can easily solve the problem.

What is "Sort elements by frequency"?

Here, Sort elements by frequency mean that the element having the most occurrence will come first, and the element with a minimum number of occurrences will come last.

What is a sorted array in a programming language?

A sorted array is a type of array data structure where each element is sorted in numerical, alphabetical, or in some other order, generally in ascending order.

Conclusion

We have extensively discussed how to Sort elements by frequency in this article. We started with an introduction, problem statement, example, pseudocode, and implementation for the given problem, and finally concluded with the time complexity of the algorithm.

Learn custom sort stringQuick sort on Doubly Linked ListDoubly Linked List, Merge Sort for Doubly Linked ListBook Allocation Problem, and many more on Coding Ninjas Studio. We hope that this blog has helped you enhance your knowledge regarding how to Sort elements by frequency.

For peeps out there who really want to learn more about Data Structures, Algorithms, Power programming languages, JavaScript, or any other upskilling, please refer to our guided paths on Coding Ninjas Studio. Enroll in our courses, and go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow.

Happy Coding!

 

Previous article
Sort an Array According to the Relative Order of Another Array
Next article
Program to find the number of misplaced elements from the index after sorting
Live masterclass