Frequency based sorting

Question

You are given an array of integers and you have sort those integers based on the frequency of
their occurrence. Design an algorithm and analyze its time complexity. In case of ties the smaller
number should appear first in the sorted list.

Sample Input: 3,4,3,2,3,5,4,2,2,1,2
Sample Output: 1 5 4 3 2

Answer 1

If extra space is allowed: go over the input and do a frequency analysis. Write it down in some hash table. That means, roughly:

for each x in input:
  if x in table:
    ++table[x]
  else
    table.insert(x)

Then, a simple Quicksort on the unique values, with the comparison function taking into account the frequency instead of the value itself.

That is:

function freq_compare (x, y):
  return compare(table[x], table[y])

Where compare is numeric for the frequencies.

Answer 2

Sort the array and then we can easily get the frequency of the numbers because the duplicate numbers will be places next to each other. As you get the frequency of the numbers insert it in a map with key as frequency and value as the number. Since map stores the keys in sorted order we can iterate the map to get the result.