Sort array based on frequency

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 ]

 

sort array

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

You might also like:

Search an element in a sorted and rotated array

HashMap Java

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

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
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x