Sorting Elements Of An Array By Frequency In Decreasing Order In Java Program

In this article, you will learn how to efficiently sort the elements of an array based on their frequency, arranging them in decreasing order, using various approaches in Java.

Problem Statement

Sorting an array by frequency in decreasing order means arranging the elements such that those appearing most frequently come first. If two elements have the same frequency, their relative order can be determined by their numerical value (typically ascending order for a consistent output). This problem is common in data analysis, log processing, and recommendation systems where identifying the most common items is crucial.

Example

Consider the input array: [2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12]

The desired output, sorted by frequency in decreasing order: [3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5] (Here, '3' appears 4 times, '2' appears 3 times, '12' appears 2 times, and '4', '5' appear once. When frequencies are equal, numbers are sorted in ascending order.)

Background & Knowledge Prerequisites

To understand the solutions presented, familiarity with the following Java concepts is beneficial:

• Arrays: Basic understanding of array declaration and manipulation.
• HashMap: Using HashMap for storing key-value pairs (element to frequency).
• ArrayList: Dynamic arrays for storing and manipulating collections of elements.
• Collections.sort(): Sorting collections using custom comparators.
• Comparator Interface: Implementing custom comparison logic.
• Java 8 Streams API: Functional programming constructs for data processing (optional for some approaches).

Use Cases or Case Studies

Sorting by frequency has numerous practical applications:

• Popularity Ranking: Identifying the most frequently purchased products in an e-commerce platform.
• Log Analysis: Finding the most common error codes or user actions in system logs.
• Text Processing: Determining the most frequent words in a document for keyword extraction or sentiment analysis.
• Network Traffic Analysis: Identifying the most active IP addresses or port numbers.
• Data Visualization: Preparing data for charts where the most frequent categories are highlighted.

Solution Approaches

Here are two effective approaches to sort an array by frequency in decreasing order in Java.

Approach 1: Using HashMap and Collections.sort with Custom Comparator

This approach involves first counting the frequency of each element using a HashMap and then sorting the distinct elements based on these frequencies using a custom Comparator.

// SortArrayByFrequencyHashMap
import java.util.ArrayList;
import java.util.Arrays;
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[] arr = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12};
        System.out.println("Original Array: " + Arrays.toString(arr));

        // Step 1: Count the frequency of each element
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Create a list of elements from the original array
        // This list will be sorted based on frequencies
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }

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

                // Compare frequencies in decreasing order
                if (freq1 != freq2) {
                    return freq2 - freq1; // For decreasing frequency
                } else {
                    // If frequencies are same, compare numbers in ascending order
                    return n1 - n2;
                }
            }
        });

        System.out.println("Sorted by Frequency (Decreasing): " + list);
    }
}

Run

Sample Output:

Original Array: [2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12]
Sorted by Frequency (Decreasing): [3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5]

Stepwise Explanation:

1. Count Frequencies: A HashMap (frequencyMap) is used to store each unique element as a key and its count as the value. We iterate through the input array, incrementing the count for each element.
2. Create List from Array: The elements of the original array are added to an ArrayList. This list will be sorted.
3. Custom Sort: Collections.sort() is used with a custom Comparator.

• The compare method of the Comparator first retrieves the frequencies of the two elements (n1, n2) from the frequencyMap.
• It then compares these frequencies: freq2 - freq1 ensures sorting in *decreasing* order of frequency (if freq2 is greater than freq1, n2 comes before n1).
• If the frequencies are equal, it falls back to comparing the numerical values of the elements themselves: n1 - n2 sorts them in *ascending* order. This provides a stable and predictable tie-breaking rule.

Approach 2: Using Java 8 Streams API (More Concise)

This approach leverages the power of Java 8 Streams for a more functional and concise way to achieve the same result.

// SortArrayByFrequencyStreams
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12};
        System.out.println("Original Array: " + Arrays.toString(arr));

        // Step 1: Count frequencies using Streams
        Map<Integer, Long> frequencyMap = Arrays.stream(arr)
                                              .boxed() // Convert int[] to Stream<Integer>
                                              .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        // Step 2: Create a list of elements from the original array
        List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());

        // Step 3: Sort the list using a custom comparator that utilizes the frequency map
        list.sort(Comparator
            .<Integer>comparing(num -> frequencyMap.get(num), Comparator.reverseOrder()) // Sort by frequency decreasing
            .thenComparing(Function.identity()) // Then by natural order (ascending value) if frequencies are equal
        );

        System.out.println("Sorted by Frequency (Decreasing) using Streams: " + list);
    }
}

Run

Sample Output:

Original Array: [2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12]
Sorted by Frequency (Decreasing) using Streams: [3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5]

Stepwise Explanation:

1. Count Frequencies with Streams:

• Arrays.stream(arr).boxed() converts the int[] to a Stream.
• Collectors.groupingBy(Function.identity(), Collectors.counting()) groups elements by their identity (the element itself) and counts their occurrences, resulting in a Map.

1. Create List from Array: The int[] is converted into a List using Arrays.stream(arr).boxed().collect(Collectors.toList()).
2. Custom Sort with Comparator Chain:

• list.sort() is called with a chained Comparator.
• Comparator.comparing(num -> frequencyMap.get(num), Comparator.reverseOrder()) sorts the elements primarily by their frequency (obtained from frequencyMap), with Comparator.reverseOrder() ensuring a decreasing order.
• .thenComparing(Function.identity()) acts as a tie-breaker. If two elements have the same frequency, it sorts them by their natural order (ascending numerical value).

Conclusion

Sorting an array by element frequency is a common problem with elegant solutions in Java. Both the traditional HashMap and Collections.sort approach and the more modern Java 8 Streams approach provide effective ways to achieve this. The choice between them often comes down to code readability, maintainability, and familiarity with functional programming paradigms.

Summary

• Problem: Arrange array elements by decreasing frequency, with ascending value as a tie-breaker.
• Core Idea: Count element frequencies first, then use these counts to guide the sorting process.
• Approach 1 (HashMap + Collections.sort):
• Use HashMap to store element -> frequency.
• Create a List of elements from the original array.
• Sort this List using a custom Comparator that prioritizes frequency (decreasing) and then element value (ascending).
• Approach 2 (Java 8 Streams):
• Use Arrays.stream().boxed().collect(Collectors.groupingBy(..., Collectors.counting())) to build the frequency map concisely.
• Convert the array to a List.
• Sort the List using a chained Comparator (comparing().thenComparing()) for frequency (decreasing) and value (ascending).
• Tie-breaking: When frequencies are equal, sorting by element value in ascending order provides a consistent and predictable result.