Sort elements by frequency

Problem: Sort elements by frequency. Sort elements of an array by frequency of the elements of the array. Sort the elements by decreasing order of their frequency. If two elements have same frequency then retain their order in input array.
For example,
If input array is 2, 5, 3, 8, 7, 2, 5, 2, 3
then output should be 2, 2, 2, 5, 5, 3, 3, 8, 7
In above output 5 and 2 occurs twice each, but 5 comes first because it appears first in the input array.

Algorithm to sort elements by frequency

We will see how to sort elements by frequency.

Say the input array is A with length n.

1. Create a frequency map for the elements of A.

2. Sort the frequency map by value. Entries in the map are sorted by value.

3. Rearrange array elements from above sorted map.

We will an example to test above algorithm.

Say given input array is {2, 5, 3, 8, 7, 2, 5, 2, 3, 3, 5, 3 }
First step: We will create frequency map.
Frequency map would look like this {2 = 3, 5 = 3, 3 = 4, 8 =1 , 7 = 1}

Second step: Sort above frequency map by value.
After sorting frequency map would be {3 = 4, 2 = 3, 5 = 3, 8 =1 , 7 = 1}

Third step: Rearrange array elements from above sorted map.
{3, 3, 3, 3, 2, 2, 2, 5, 5, 5, 8, 7}

Java code:

We will see Java code implementation of above algorithm to sort elements by frequency.
In below code we are using custom sorter to sort map by value.

package com.javafries.array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class SortByFrequencyProblem {

	private static void sortByFrequency(int[] arr) {
		Map<Integer, Integer> frequencyMap = createFrequencyMap(arr);

		List<Entry<Integer, Integer>> entryList = sortByValue(frequencyMap);

		putSortedElementsBackInArray(arr, entryList);
	}

	private static Map<Integer, Integer> createFrequencyMap(int[] arr) {

		// Use LinkedHashMap because it maintains insertion order of elements.
		Map<Integer, Integer> frequencyMap = new LinkedHashMap<>();

		for (int i = 0; i < arr.length; i++) {
			int key = arr[i];
			if (frequencyMap.containsKey(key)) {
				frequencyMap.put(key, frequencyMap.get(key) + 1);
			} else {
				frequencyMap.put(key, 1);
			}
		}
		return frequencyMap;
	}

	private static List<Entry<Integer, Integer>> sortByValue(
			Map<Integer, Integer> frequencyMap) {

		// List containing elements of map's entry set.
		List<Entry<Integer, Integer>> entryList = new ArrayList<Entry<Integer, Integer>>(
				frequencyMap.entrySet());

		// Sort the list.
		Collections.sort(entryList,
				new Comparator<Map.Entry<Integer, Integer>>() {

					@Override
					public int compare(Entry<Integer, Integer> o1,
							Entry<Integer, Integer> o2) {
						return o2.getValue().compareTo(o1.getValue());
					}
				});
		return entryList;
	}

	private static void putSortedElementsBackInArray(int[] arr,
			List<Entry<Integer, Integer>> list) {
		int index = 0;

		// Arrange array elements in sorted list of entry set of frequency map.
		for (Map.Entry<Integer, Integer> entry : list) {
			for (int i = 0; i < entry.getValue(); i++) {
				arr[index++] = entry.getKey();
			}
		}
	}

	private static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	public static void main(String[] args) {
		int[] arr = { 2, 5, 3, 8, 7, 2, 5, 2, 3, 3, 5, 3 };

		System.out.println("Input array before sorting elements by frequency.");
		printArray(arr);

		sortByFrequency(arr);

		System.out.println();
		System.out.println();

		System.out.println("Array after sorting elements by frequency.");
		printArray(arr);
	}
}

Output:

Input array before sorting elements by frequency.
2 5 3 8 7 2 5 2 3 3 5 3 

Array after sorting elements by frequency.
3 3 3 3 2 2 2 5 5 5 8 7

 

I hope you liked and understood the solution. I have tried to keep the solution simple.
Your comments and questions are most welcome.

Leave a Reply