Example: Sort Array by Frequency in Java

// 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]
    }
}