Sorting Elements by Frequency in an Array: A Complete Guide

Sorting Elements by Frequency in an Array: A Complete Guide

Sorting elements by frequency is a common task in programming, where the goal is to reorder elements in a way that reflects their occurrences in the input. If two elements have the same frequency, the one that appears first in the input retains its position. This article explores multiple methods to solve this problem efficiently, covering sorting, hashing, and map-based approaches.Sorting Elements by Frequency in an Array

Problem Statement

Given an array of integers, sort its elements in decreasing order of their frequency. If two elements have the same frequency, retain their relative order from the input.

Example Test Cases

Test Case 1:

Input: 2,3,2,4,5,12,2,3,3,3,122, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12Output: 3,3,3,3,2,2,2,12,12,4,53, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5

Test Case 2:

Input: 1,2,3,2,1,1,4,5,6,61, 2, 3, 2, 1, 1, 4, 5, 6, 6Output: 1,1,1,2,2,6,6,3,4,51, 1, 1, 2, 2, 6, 6, 3, 4, 5

Approaches to Solve the Problem

1. Using Sorting

Algorithm:
  1. Count the frequency of each element using a nested loop or any counting mechanism.
  2. Sort the elements by frequency in descending order.
  3. If two elements have the same frequency, maintain their relative order from the input (stable sorting).
Time Complexity: O(n2)O(n^2) due to nested loops for counting frequencies.

2. Using Hashing

Algorithm:
  1. Use a hash map to store the frequency of each element.
  2. Create a sorted array based on frequency values.
  3. For elements with the same frequency, retain their relative order by indexing during the sorting phase.
Time Complexity: O(nlog⁡n)O(n \log n) for sorting.

3. Using Maps/Binary Search Tree (BST)

Algorithm:
  1. Use a tree map or similar data structure to count frequencies while maintaining sorted order.
  2. Store elements in buckets or lists based on their frequency.
  3. Output the elements in the required order.
Time Complexity: O(nlog⁡n)O(n \log n) for map operations.

Python Implementation

Using Hashing and Sorting

python
from collections import Counterdef sort_by_frequency(arr): """ Sort elements by frequency in descending order. Args: arr (list): Input array of integers. Returns: list: Array sorted by frequency. """ # Count frequency using Counter freq = Counter(arr)# Sort by frequency (descending) and by index (ascending for ties) sorted_arr = sorted(arr, key=lambda x: (-freq[x], arr.index(x)))return sorted_arr# Example Test Cases print(sort_by_frequency([2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12])) # Output: [3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5] print(sort_by_frequency([1, 2, 3, 2, 1, 1, 4, 5, 6, 6])) # Output: [1, 1, 1, 2, 2, 6, 6, 3, 4, 5]

Breakdown of Example

Input: 2,3,2,4,5,12,2,3,3,3,122, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12
  1. Step 1: Count frequencies: {2:3,3:4,4:1,5:1,12:2}\{2: 3, 3: 4, 4: 1, 5: 1, 12: 2\}
  2. Step 2: Sort elements by frequency: 3,3,3,3,2,2,2,12,12,4,53, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5

Visualization and SEO-Optimized Suggestions

Subheadings:

  1. What is Frequency Sorting?
  2. Efficient Algorithms for Sorting by Frequency
  3. Step-by-Step Explanation with Examples
  4. Python Code for Frequency Sorting
  5. Applications of Frequency Sorting in Real Life
Click here to know more our program!Sorting Elements by Frequency in an Array
c