Trusted answers to developer questions

Educative Answers Team

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:

This method relies primarily on sorting the given input.

- Sort the given input.
- 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.
- 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:

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.

This method makes use of hashing and sorting.

- 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.
- 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.

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.

RELATED TAGS

frequency sort

algorithm

Copyright Â©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses