Sort array based on frequency

Question:
Given the array, sort the array based on the frequency in descending order. If two elements have the same frequency, then sort based on their values. Note: 3 occurs two times in array then frequency(3) = 2.
Sample 1:
Input : [5, 3, 2, 2, 1, 7, 9, 5, 3, 2, 1, 3]
Output: [ 2, 2, 2, 3, 3, 3, 1, 1, 5, 5, 7, 9 ]
Logic:
- Create Hash-Map with elements as a key and their frequency as value
- Then insert elements into the Hash-Map by calculating their corresponding frequency
- Create Array List which contains the Hash-Map Values
- Sort the array list based on frequency using Collections
- Print the sorted value
Explanation:
Program:
Java:
[code lang=”java”]
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class SortArrayByFrequency
{
private static void sortArrayByFrequency(int[] array)
{
//Create HashMap with elements as key and their frequency as value
Map<Integer, Integer> element = new HashMap<>();
int frequency;
//Insert the array Elements into the HashMap
for (int i = 0; i < array.length; i++)
{
//Check the key is already present in the HashMap
if (element.containsKey(array[i]))
{
//Increment the Value if it is already present
element.put(array[i], element.get(array[i])+1);
}
else
{
//Insert the Key and value as 1
element.put(array[i], 1);
}
}
//Create ArrayList with HashMap Values
ArrayList<Entry<Integer, Integer>> list = new ArrayList<>(element.entrySet());
Collections.sort(list, new Comparator<Entry<Integer, Integer>>()
{
@Override
public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2)
{
//Check the frequency is equal and Swap the values
if(o2.getValue() == o1.getValue())
{
if(o2.getKey() < o1.getKey())
{
return 1;
}
else
return -1;
}
return o2.getValue().compareTo(o1.getValue());
}
});
//Print the Vales based on frequnency
for (Entry<Integer, Integer> entry : list)
{
frequency = entry.getValue();
for(int count = 0; count < frequency; count++)
{
System.out.print(entry.getKey()+" ");
}
}
}
public static void main(String[] args)
{
sortArrayByFrequency(new int[] {5, 3, 2, 2, 1, 7, 9, 5, 3, 2, 1, 3});
}
}
[/code]
Approach 2:
- Create a structure with key and value parameters
- Calculate the frequency of each element and insert into the struct array of key and value
- Sort the array based on frequency, if frequency is equal then sort based on key element
- Print the sorted array value
C:
[code lang=”c”]
#include<stdio.h>
struct map
{
int key;
int value;
};
void swap(struct map **value1,struct map **value2)
{
struct map *temp = *value1;
*value1 = *value2;
*value2 = temp;
}
void main()
{
int arr[] = {5,3,2,2,1,7,9,5,3,2,1,3};
int length = sizeof(arr)/sizeof(arr[0]);
struct map mapList[length];
int i,j,index = -1;
int temp;
//find the frequency of each element
for(i = 0; i < length; i++)
{
if(arr[i] != -1)
{
index++;
mapList[index].key = arr[i];
mapList[index].value = 1;
}
else
{
continue;
}
for(j = i + 1; j< length; j++)
{
if(arr[i] == arr[j])
{
mapList[index].value++;
arr[j] = -1;
}
}
}
for(i = 0;i<=index;i++)
printf("value:%d frequency:%d\n",mapList[i].key,mapList[i].value);
//sort the array based on frequency
for(i = 0; i <= index; i++)
{
for(j = i + 1; j <= index; j++)
{
if(mapList[i].value == mapList[j].value)
{
if(mapList[i].key > mapList[j].key)
{
swap(&mapList[i],&mapList[j]);
}
}
else if(mapList[i].value < mapList[j].value)
{
swap(&mapList[i],&mapList[j]);
}
}
}
//print the value
for(i = 0;i<=index;i++)
{
for(j = 0; j < mapList[i].value; j++)
{
printf("%d ",mapList[i].key);
}
}
}
[/code]