Sort elements in array by frequency

February 8, 2021

Sort elements in an array by frequency in Java.

Problem statement:

Sort array elements in such a way that the element with the highest number of occurrences comes first. If the number of occurrences is equal then print the number which appeared first in the array.

Example:

Input:

a[ ] = {2, 5, 2, 8, 5, 6, 8, 8}

Output:

a[ ] = {8, 8, 8, 2, 2, 5, 5, 6}

Algorithm:( Using Java Map)

Get the element with its count in a Map
Use Comparator Interface, compare the frequency of an element in a given list.
Use this comparator to sort the list by implementing the Collections. sort() method.
Print the sorted list.

Java code :

import java.util.*; 

public class prepinsta { 

    // Driver Code 
    public static void main(String[] args) 
    { 

        // Declare and Initialize an array 
        int[] array = {2, 5, 2, 8, 5, 6, 8, 8} 

        Map<Integer, Integer> map = new HashMap<>(); 
        List<Integer> fnlArray = new ArrayList<>(); 

        
        for (int current : array) { 
            int count = map.getOrDefault(current, 0); 
            map.put(current, count + 1); 
            fnlArray.add(current); 
        } 

        // Compare the map by value 
        SortComparator comp = new SortComparator(map); 

        // Sort the map using Collections CLass 
        Collections.sort(fnlArray, comp); 

    
        for (Integer i : fnlArray) { 
            System.out.print(i + ” “); 
        } 
    } 
} 


class SortComparator implements Comparator<Integer> { 
    private final Map<Integer, Integer> freqMap; 

    
    SortComparator(Map<Integer, Integer> tFreqMap) 
    { 
        this.freqMap = tFreqMap; 
    } 

    // Compare the values 
    @Override
    public int compare(Integer p1, Integer p2) 
    { 

        // Compare value by frequency 
        int freqCompare = freqMap.get(p2).compareTo(freqMap.get(p1)); 

        // Compare value if frequency is equal 
        int valueCompare = p1.compareTo(p2); 

        // If frequency is equal, then just compare by value, otherwise – 
        // compare by the frequency. 
        if (freqCompare == 0) 
            return valueCompare; 
        else
            return freqCompare; 
    } 
} 

Output:

{8, 8, 8, 2, 2, 5, 5, 6}