Sort elements by frequency (using Java Map)

Software Development
#1

Hello Everyone,

Given an integer array, sort the array according to the frequency of elements in decreasing order, if frequency of two elements are same then sort in increasing order

Examples:

Input: arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}
Output: 3 3 3 3 2 2 2 12 12 4 5
Explanation :
No. Freq
2 : 3
3 : 4
4 : 1
5 : 1
12 : 2

Input: arr[] = {4, 4, 2, 2, 2, 2, 3, 3, 1, 1, 6, 7, 5}
Output: 2 2 2 2 1 1 3 3 4 4 5 6 7

Approach:

Java Map has been used in this set to solve the problem. The java.util.Map interface represents a mapping between a key and a value. The Map interface is not a subtype of the Collection interface. Therefore it behaves a bit different from the rest of the collection types.

In the below program:

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

Program:

import java.util.*;

public class GFG {

// Driver Code

public static void main(String[] args)

{

// Declare and Initialize an array

int [] array = { 4 , 4 , 2 , 2 , 2 , 2 , 3 , 3 , 1 , 1 , 6 , 7 , 5 };

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

List<Integer> outputArray = new ArrayList<>();

// Assign elements and their count in the list and map

for ( int current : array) {

int count = map.getOrDefault(current, 0 );

map.put(current, count + 1 );

outputArray.add(current);

}

// Compare the map by value

SortComparator comp = new SortComparator(map);

// Sort the map using Collections CLass

Collections.sort(outputArray, comp);

// Final Output

for (Integer i : outputArray) {

System.out.print(i + " " );

}

}

}

// Implement Comparator Interface to sort the values

class SortComparator implements Comparator<Integer> {

private final Map<Integer, Integer> freqMap;

// Assign the specified map

SortComparator(Map<Integer, Integer> tFreqMap)

{

this .freqMap = tFreqMap;

}

// Compare the values

@Override

public int compare(Integer k1, Integer k2)

{

// Compare value by frequency

int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));

// Compare value if frequency is equal

int valueCompare = k1.compareTo(k2);

// If frequency is equal, then just compare by value, otherwise -

// compare by the frequency.

if (freqCompare == 0 )

return valueCompare;

else

return freqCompare;

}

}

Output:

2 2 2 2 1 1 3 3 4 4 5 6 7

Time Complexity : O(n Log n)