Java Program For Sorting Elements Of An Array By Frequency

Sorting an array by frequency means arranging its elements based on how many times each element appears. This technique is crucial for various data analysis and processing tasks, allowing you to prioritize or organize data based on prevalence. In this article, you will learn how to implement a Java program to sort array elements by their frequency.

Problem Statement

In many real-world scenarios, understanding the distribution of elements within a dataset is vital. For example, in log analysis, identifying the most frequent error messages can help pinpoint critical issues. Similarly, in e-commerce, knowing the most frequently purchased items can inform inventory management. The core problem is to transform an unsorted array into one where elements appearing more often come first, and elements with the same frequency are sorted by their value.

Example

Consider an input array: [1, 2, 3, 2, 1, 4, 1]

The expected output after sorting by frequency would be: [1, 1, 1, 2, 2, 3, 4]

Here's why:

• 1 appears 3 times.
• 2 appears 2 times.
• 3 appears 1 time.
• 4 appears 1 time.

Elements with higher frequencies (like 1) appear first. If frequencies are equal (3 and 4), they are sorted by their numerical value.

Background & Knowledge Prerequisites

To understand and implement the solutions effectively, familiarity with the following Java concepts is beneficial:

• Arrays: Basic operations like declaration, initialization, and iteration.
• HashMap: For storing key-value pairs (element and its frequency).
• ArrayList: A dynamic array used to hold elements and facilitate sorting with custom comparators.
• Collections.sort(): A utility method for sorting lists.
• Comparator Interface: For defining custom sorting logic.

Use Cases or Case Studies

Sorting elements by frequency has numerous practical applications across various domains:

• Data Analysis: Identifying the most common words in a text document, top-selling products in a store, or most frequent errors in system logs.
• Recommendation Systems: Suggesting items that are frequently purchased together or viewed by many users.
• Search Engine Optimization (SEO): Analyzing keyword density to optimize content for relevant search terms.
• Network Traffic Analysis: Pinpointing the most active IP addresses or heavily used ports to detect anomalies or optimize network performance.
• Image Processing: Analyzing color frequency to reduce palette sizes or identify dominant colors.

Solution Approaches

Approach 1: Using HashMap and Custom Comparator

This approach involves two main steps: first, counting the frequency of each element using a HashMap, and then sorting the array elements based on these frequencies using a custom Comparator.

One-line Summary

Count element frequencies using a HashMap and then sort the array's elements by those frequencies (descending), breaking ties by element value (ascending).

Code Example

// Sort Array Elements by Frequency
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// Main class containing the entry point of the program
public class Main {

    public static void main(String[] args) {
        int[] originalArray = {1, 2, 3, 2, 1, 4, 1, 5, 5, 5};

        System.out.println("Original Array:");
        printArray(originalArray);

        // Step 1: Convert int[] to List<Integer>
        List<Integer> list = new ArrayList<>();
        for (int num : originalArray) {
            list.add(num);
        }

        // Step 2: Calculate frequency of each element using a HashMap
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : list) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 3: Sort the list using a custom Comparator
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer n1, Integer n2) {
                int freq1 = frequencyMap.get(n1);
                int freq2 = frequencyMap.get(n2);

                // Primary sort: by frequency (descending)
                if (freq1 != freq2) {
                    return freq2 - freq1; // Higher frequency comes first
                } else {
                    // Secondary sort: by value (ascending) if frequencies are equal
                    return n1 - n2; // Smaller value comes first
                }
            }
        });

        System.out.println("\\nArray sorted by Frequency:");
        printList(list);
    }

    // Helper method to print an int array
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + (i == arr.length - 1 ? "" : ", "));
        }
        System.out.println();
    }

    // Helper method to print a List of Integers
    public static void printList(List<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + (i == list.size() - 1 ? "" : ", "));
        }
        System.out.println();
    }
}

Run

Sample Output

Original Array:
1, 2, 3, 2, 1, 4, 1, 5, 5, 5

Array sorted by Frequency:
1, 1, 1, 5, 5, 5, 2, 2, 3, 4

Stepwise Explanation

1. Convert to List: An int[] array is first converted into a List. This is necessary because Collections.sort() operates on List objects, not primitive arrays, and allows for custom Comparator implementations.
2. Calculate Frequencies: A HashMap named frequencyMap is used to store the count of each element. It iterates through the list, and for each number, it either increments its existing count or initializes it to 1 if it's encountered for the first time. getOrDefault(key, defaultValue) is a convenient method for this.
3. Define Custom Comparator: An anonymous inner class implementing Comparator is created. The compare(Integer n1, Integer n2) method defines the sorting logic:

• It retrieves the frequencies of n1 and n2 from the frequencyMap.
• Primary Sort: It compares freq1 and freq2. If they are different, it returns freq2 - freq1. A positive result means n2 has a higher frequency and should come before n1 (descending order of frequency).
• Secondary Sort (Tie-breaker): If freq1 and freq2 are equal, it means both numbers appear the same number of times. In this case, it performs a secondary sort based on the numerical value of the elements themselves, returning n1 - n2. A positive result means n2 is smaller and should come before n1 (ascending order of value).

1. Sort the List: Collections.sort(list, new Comparator() { ... }); applies the custom sorting logic to the list, effectively arranging its elements by frequency.
2. Print Results: Helper methods printArray and printList are used to display the original and sorted arrays for verification.

Conclusion

Sorting an array by the frequency of its elements is a common requirement in data processing. The Java approach using a HashMap to count frequencies and a custom Comparator with Collections.sort() offers a clear, efficient, and flexible way to achieve this. This method allows for precise control over the sorting criteria, including handling tie-breaking scenarios.

Summary

• Sorting by frequency arranges elements based on their occurrences, with more frequent elements appearing first.
• A HashMap is an excellent tool for efficiently counting element frequencies.
• List and Collections.sort() are used for flexible sorting in Java.
• A custom Comparator is essential for defining multi-level sorting logic: primary by frequency (descending), and secondary by value (ascending) for ties.
• This technique is widely applicable in data analysis, logging, and recommendation systems.