The frequency sort algorithm

The frequency sort algorithm is used to output elements of an array in descending order of their frequencies.

If two elements have the same frequencies, then the element that occurs first in the input is printed first.

The frequency sort algorithm can be implemented in many ways. Below are two popular methods:

Solution: using an array

This method relies primarily on sorting the given input.

Steps

1. Sort the given input.
2. Loop over the sorted input and keep track of each distinct element, the number of times it occurs, and the index at which it first occurred in the input.
3. Sort this array based on the values of the frequency of occurrence of each element. Whenever two elements have the same frequency, put the element with the lower index in the output first.

The following illustration shows how this method works:

Time Complexity

Assuming that the sorting algorithm takes $O(n log(n))$, where n is the number of elements in the input, then method one takes $O(n log(n))$ + $O(n)$ + $O(m log(m))$ = $O(n log(n))$. Note that $m$ denotes the number of distinct elements in the input.

Solution: using a hash table

This method makes use of hashing and sorting.

Steps

1. Hash all the elements and store their occurrence frequencies along with the index of their first occurrence. Note that the elements are the keys, while their frequency and index value is the value.
2. Sort the entries in the hash table based on the occurrence frequency values of each element. Whenever two elements have the same frequency, put the element with the lower index in the output first.

Time Complexity

Assuming that the sorting algorithm takes $O(n log(n))$, where n is the number of elements in the input, then method two takes $O(n)$ + $O(m log(m))$, where $m$ denotes the number of distinct elements in the input.