## Sorting By Frequency

### January 5, 2018

We have another homework question today, as I continue clearing out my backlog of people who sent me email asking for homework help last fall:

You are given an array with duplicates, and are to sort the array by decreasing frequency of elements. If two elements have the frequency, sort them in increasing order of value. For instance, the input (2 3 5 3 7 9 5 3 7) is sorted as (3 3 3 5 5 7 7 2 9).

Your task is to write a program that sorts by frequency. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Here is an O(n log n) solution (with the usual hash-table caveat)

using R7RS Scheme and a couple of popular SRFIs (for hash-tables and

sorting).

I don’t see that append or mappend should be quadratic. Classic implementation: scan forwards down list, but build up result in reverse.

Here’s a Haskell version. First we create a mapping from each list element to a count of how many time it occurs. We convert the map to its corresponding list of key/value pairs, which is sorted using a comparison function that ensures the order we want. Finally, each pair (x, n) in the sorted list is replaced by a list of n copies of x, then the result is concatenated.

Here’s a solution in Python.

Output:

Another solution in Python. This one sorts the items of the Counter, not all items from the original array.

Here’s another Haskell solution then. Sort the list, group into sublists of identical element. Concatenate while wrapping each element in a tuple with the count of identical elements (this is negated so we can use the standard tuple ordering for sorting). Sort and drop the count. Seems to run in about the same time as Globules’ solution above, depending on the amount of duplication.

Here are two Python approaches with and without Counter respectively. Although less elegant, the latter is more fun trying to figure out.

Sol. 1 (with Counter)

Sol.2 (without Counter)