Sort Elements by Frequency in Java
To sort the elements in Java by using frequency, we need an input array. We should create a function that sorts the elements in an array by using their frequencies in descending or ascending order. We have to print the elements that first appear in the list, and if the element is repeated two or more times, then we should follow the following order:
Input array: [17, 11, 13, 14, 17, 11, 17, 11, 14, 15, 11, 19, 13]
The output array in sorted according to the frequency in ascending order:
Output array: [11, 11, 11, 11, 17, 17, 17, 13, 13, 14, 14, 15, 19].
Each component occurs exactly once or at frequency 1. As a result, the order in which the elements appear in the input array matches the order in which they appear in the output array.
Algorithm or step-by-step sequence:
Step 1: First, create a LinkedHashMap with the name countele. The elements in the countele are keys and their frequencies are values.
Step 2: now check each element of the arr in the countele. If the element is found or present in the countele, then we have to increment the count or frequency by 1. Otherwise, we have to insert the element with 1 as its value.
Step 3: now create or construct an arraylist called entrylist which holds or responsible of holding all the entry objects of countele.
Step 4: based on values of the entry objects we have to sort the entrylist.
Here we will use a function named Collections.sort() which sort the elements in the list or array.
Step 5: at last, the entrylist consist of all the elements in the sorted order based on their frequency and we have to print them in the decreasing or increasing order as their frequencies.
Example code:
The implementation of steps above in algorithm are performed via code.
import java.util.*;
import java.util.Arrays;
import java.io.*;
import java.util.Collections;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Map;
import java.util.LinkedHashMap;
import java.util.Map.Entry;
public class frequencysort
{
private static void frequencysort(int[] arr)
{
//Create a LinkedHashMap with the elements' occurrences as values and keys. Keep in mind that LinkedHashMap preserves element insertion order.
Map<Integer, Integer> counteleMap = new LinkedHashMap<>();
//Check the number or value existsin countele
for (int i = 0; i < arr.length; i++)
{
if (counteleMap.containsKey(arr[i]))
{
//if the presence of element in the countele then we have to increament by 1
counteleMap.put(arr[i], counteleMap.get(arr[i])+1);
}
else
{
//If the presence of element is not there in countele then, insert the value element with 1 as its value.
counteleMap.put(arr[i], 1);
}
}
// now create an arraylist which holds all the values in the countelemap with an entry of object.
ArrayList<Entry<Integer, Integer>> entrylist = new ArrayList<>(counteleMap.entrySet());
//Sort the entrylist based on values
Collections.sort(entrylist, new Comparator<Entry<Integer, Integer>>()
{
@Override
public int compare(Entry<Integer, Integer> a, Entry<Integer, Integer> b)
{
return b.getValue().compareTo(a.getValue());
}
}
);
//print the sorted array list in the increasing order or desecnding order according to the frequency.
System.out.println("the input array is : "+Arrays.toString(arr));
System.out.println("sorted array list in the increasing order or desecnding order according to the frequency :");
System.out.print("[ ");
for (Entry<Integer, Integer> entry : entrylist)
{
int freq = entry.getValue();
while (freq >= 1)
{
System.out.print(entry.getKey()+" ");
freq--;
}
}
System.out.print("]");
}
public static void main(String[] args)
{
frequencysort(new int[] {17, 11, 13, 14, 17, 11, 17, 11, 14, 15, 11, 19, 13});
}
}
Output:
cd /home/cg/root/6368984ad6872
the input array is : [17, 11, 13, 14, 17, 11, 17, 11, 14, 15, 11, 19, 13]
sorted array list in the increasing order or desecnding order according to the frequency :
[ 11 11 11 11 17 17 17 13 13 14 14 15 19 ]
Complexity analysis for the above program is calculated based on the number of occurrences and swap:
The program has an O(n * log(n)) time complexity because sorting is being used. Additionally, an array list was made to house the outcomes. Consequently, the space complexity becomes O(n), where n is the total number of elements in the input array.