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:
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}); } }
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:
#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); } } }