# 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

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

## HashMap Java

### Vignesh

A Computer Science graduate who likes to make things simpler. When he’s not working, you can find him surfing the web, learning facts, tricks and life hacks. He also enjoys movies in his leisure time.
5 1 vote
Article Rating
Subscribe
Notify of