Sorting Elements Of An Array By Frequency In Java

Sorting an array by the frequency of its elements is a common task in programming that requires understanding data structures and custom sorting logic. This process involves rearranging array elements so that those appearing most frequently come first, with a tie-breaking rule often applied for elements with the same frequency.

In this article, you will learn how to sort elements of an array by their frequency in Java, exploring a robust solution using HashMaps and custom Comparators, along with practical examples and use cases.

Problem Statement

Consider an array of integers, for example, [1, 1, 2, 3, 2, 1]. The goal is to reorder this array such that elements with higher frequencies appear first. If two elements have the same frequency, they should be sorted in ascending order of their value.

For the given example: - 1 appears 3 times. - 2 appears 2 times. - 3 appears 1 time.

A simple sort by value would yield [1, 1, 1, 2, 2, 3]. However, when sorting by frequency first (descending), then by value (ascending), the desired output remains [1, 1, 1, 2, 2, 3] because 1 has the highest frequency, followed by 2, then 3.

Example

Let's illustrate the expected output for a different input:

Input Array: [2, 5, 2, 8, 5, 6, 8, 8]

Frequencies: - 2: 2 times - 5: 2 times - 6: 1 time - 8: 3 times

Sorting by frequency (descending) first, then by value (ascending) for ties:

1. 8 (3 times)
2. 2 (2 times)
3. 5 (2 times)
4. 6 (1 time)

Output Array: [8, 8, 8, 2, 2, 5, 5, 6]

Background & Knowledge Prerequisites

To effectively sort an array by frequency in Java, a solid understanding of the following concepts is essential:

• Java Collections Framework Basics: Familiarity with List (specifically ArrayList) and Map (specifically HashMap).
• HashMap: How to use HashMap to store key-value pairs (e.g., element and its frequency).
• ArrayList: Creating, adding elements, and iterating through ArrayList objects.
• Collections.sort(): How to sort List implementations using Collections.sort().
• Comparator Interface: Implementing the Comparator interface to define custom sorting logic for objects. This is crucial for multi-level sorting (first by frequency, then by value).

Relevant imports for the solution will include java.util.Map, java.util.HashMap, java.util.List, java.util.ArrayList, and java.util.Collections, java.util.Comparator.

Use Cases or Case Studies

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

• Data Analysis: Identifying the most frequently occurring data points in a dataset, such as top-selling products, most common error codes, or popular search queries.
• Text Processing: Determining the frequency of words in a document for natural language processing tasks, keyword extraction, or creating word clouds.
• Database Query Optimization: Analyzing column value distributions to optimize indexing strategies or query plans.
• Recommendation Systems: Suggesting items based on their popularity or the frequency of user interactions.
• Log Analysis: Pinpointing the most common events or actions in system logs to diagnose issues or understand user behavior patterns.

Solution Approaches

There are several ways to approach this problem in Java. We will focus on a highly effective method using HashMap and a custom Comparator, and briefly touch upon other variations.

Approach 1: Using HashMap and Custom Comparator

This approach involves two main steps: first, counting the frequency of each element, and second, sorting the unique elements based on these frequencies using a custom comparator.

One-line summary: Count element frequencies using a HashMap, then sort unique elements by frequency (descending) and value (ascending) using a custom Comparator, finally reconstruct the array.

// Sort Array 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;

public class Main {

    /**
     * Sorts an array of integers by frequency in descending order.
     * If frequencies are equal, elements are sorted by value in ascending order.
     *
     * @param arr The input integer array.
     * @return A new List containing elements sorted by frequency.
     */
    public static List<Integer> sortByFrequency(int[] arr) {
        // Step 1: Count frequencies of each element using a HashMap
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Create a list of unique elements from the array
        // This list will be sorted based on frequency and then value
        List<Integer> uniqueElements = new ArrayList<>(frequencyMap.keySet());

        // Step 3: Sort the uniqueElements list using a custom Comparator
        Collections.sort(uniqueElements, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                // Get frequencies of elements 'a' and 'b'
                int freqA = frequencyMap.get(a);
                int freqB = frequencyMap.get(b);

                // Primary sort: by frequency in descending order
                if (freqA != freqB) {
                    return freqB - freqA; // For descending frequency
                } else {
                    // Secondary sort: if frequencies are equal, sort by element value in ascending order
                    return a - b; // For ascending value
                }
            }
        });

        // Step 4: Reconstruct the final sorted list based on the sorted uniqueElements
        List<Integer> sortedList = new ArrayList<>();
        for (Integer element : uniqueElements) {
            int frequency = frequencyMap.get(element);
            for (int i = 0; i < frequency; i++) {
                sortedList.add(element);
            }
        }
        return sortedList;
    }

    public static void main(String[] args) {
        // Example 1
        int[] arr1 = {1, 1, 2, 3, 2, 1};
        System.out.println("Original Array 1: " + java.util.Arrays.toString(arr1));
        List<Integer> result1 = sortByFrequency(arr1);
        System.out.println("Sorted by Frequency 1: " + result1); // Expected: [1, 1, 1, 2, 2, 3]

        // Example 2
        int[] arr2 = {2, 5, 2, 8, 5, 6, 8, 8};
        System.out.println("\\nOriginal Array 2: " + java.util.Arrays.toString(arr2));
        List<Integer> result2 = sortByFrequency(arr2);
        System.out.println("Sorted by Frequency 2: " + result2); // Expected: [8, 8, 8, 2, 2, 5, 5, 6]

        // Example 3
        int[] arr3 = {1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5};
        System.out.println("\\nOriginal Array 3: " + java.util.Arrays.toString(arr3));
        List<Integer> result3 = sortByFrequency(arr3);
        System.out.println("Sorted by Frequency 3: " + result3); // Expected: [1, 1, 1, 4, 4, 4, 2, 2, 5, 5, 3]
    }
}

Run

Sample Output:

Original Array 1: [1, 1, 2, 3, 2, 1]
Sorted by Frequency 1: [1, 1, 1, 2, 2, 3]

Original Array 2: [2, 5, 2, 8, 5, 6, 8, 8]
Sorted by Frequency 2: [8, 8, 8, 2, 2, 5, 5, 6]

Original Array 3: [1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5]
Sorted by Frequency 3: [1, 1, 1, 4, 4, 4, 2, 2, 5, 5, 3]

Stepwise Explanation:

1. Count Frequencies: A HashMap named frequencyMap is used to store each element of the input array as a key and its count as the value. We iterate through the input array, incrementing the count for each element. getOrDefault is a convenient method for this.
2. Extract Unique Elements: An ArrayList called uniqueElements is created, populated with the keys (unique elements) from the frequencyMap. This list represents the distinct numbers that need to be sorted.
3. Custom Sort: The Collections.sort() method is applied to uniqueElements. It takes a Comparator as an argument, allowing us to define custom sorting rules.

• Inside the compare method of the Comparator, we retrieve the frequencies (freqA, freqB) of the two elements (a, b) being compared from frequencyMap.
• Primary Sort: The elements are first sorted by frequency in *descending* order (freqB - freqA). A positive result means b comes before a (higher frequency first).
• Secondary Sort (Tie-breaker): If the frequencies are equal (freqA == freqB), elements are then sorted by their *value* in *ascending* order (a - b). A positive result means b comes before a (smaller value first).

1. Reconstruct Result: A new ArrayList named sortedList is created. We iterate through the uniqueElements list (which is now sorted by frequency and value). For each element, we retrieve its frequency from frequencyMap and add the element to sortedList that many times. This reconstructs the array with elements sorted by their frequency.

Approach 2: Using a Custom Class and Comparator (Brief)

This approach involves creating a custom class (e.g., ElementFrequency) to hold both the element's value and its frequency.

1. Count frequencies into a HashMap as before.
2. Convert the HashMap entries into an ArrayList of ElementFrequency objects.
3. Sort this ArrayList using Collections.sort and a Comparator that compares ElementFrequency objects. The Comparator would have similar logic to Approach 1, comparing frequency first, then element.
4. Iterate through the sorted ArrayList of ElementFrequency objects to build the final list.

This approach offers better encapsulation but involves creating an extra class.

Approach 3: Using Java 8 Streams (Brief)

For Java 8 and newer, streams provide a more concise way to achieve the same:

1. Count frequencies using Collectors.groupingBy and Collectors.counting.
2. Transform the map into a List of elements, then sort this list using a custom Comparator (similar to Approach 1) that references the frequency map.
3. Use flatMap to repeat elements according to their frequency.

While more compact, the stream solution can sometimes be less straightforward for beginners to debug or understand the multi-level sorting logic compared to explicit loops and Collections.sort.

Conclusion

Sorting an array by the frequency of its elements is a practical problem often solved by leveraging Java's Collections Framework. The combination of HashMap for efficient frequency counting and a custom Comparator with Collections.sort() provides a flexible and powerful way to implement complex sorting logic, including tie-breaking rules. This method ensures that elements are ordered first by how often they appear, and then by their natural order when frequencies are identical.

Summary

• Problem: Reorder an array based on element frequency (descending), with element value (ascending) as a tie-breaker.
• Key Tool 1 (HashMap): Used to efficiently count the occurrences of each unique element in the array.
• Key Tool 2 (ArrayList of Unique Elements): Created from HashMap keys to hold distinct elements that need sorting.
• Key Tool 3 (Collections.sort() with Comparator): Essential for applying custom sorting rules. The Comparator defines how two elements are compared:
• Primary comparison: Frequencies (descending).
• Secondary comparison: Element values (ascending) if frequencies are equal.
• Reconstruction: After sorting the unique elements, iterate through the sorted unique elements and add each element to a new list the number of times it appeared in the original array.
• Alternatives: Custom wrapper classes or Java 8 Streams can also be used, offering different trade-offs in terms of verbosity and functional style.