Sort Elements by Frequency in an Array | Step-by-Step 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.

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,12$

Output:
$3,3,3,3,2,2,2,12,12,4,5$

Test Case 2:

Input:
$1,2,3,2,1,1,4,5,6,6$

Output:
$1,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)O(n2) 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(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(n\log n)$ for map operations.

Python Implementation

Using Hashing and Sorting

Breakdown of Example

Input: $2,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. Step 2: Sort elements by frequency:
   $3,3,3,3,2,2,2,12,12,4,5$