Frequency based sorting

You are given an array of integers and you have sort those 开发者_StackOverflowintegers 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

---

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.

---

Sort the array and then we can easily get the frequency of the numbers because the duplicate numbers will be placed 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.

---

First make HashMap,putting array element as key and their frequency as values. Sort them using Comparator based on keys and values.

import java.io.*;
import java.util.*;
import java.lang.*;
public class Sum_of
{
 public static HashMap<Integer, Integer> sortHashMapByValues(
    HashMap<Integer, Integer> passedMap) {
List<Integer> mapKeys = new ArrayList<>(passedMap.keySet());
List<Integer> mapValues = new ArrayList<>(passedMap.values());
Collections.sort(mapValues);
Collections.sort(mapKeys);

LinkedHashMap<Integer, Integer> sortedMap =
    new LinkedHashMap<>();

Iterator<Integer> valueIt = mapValues.iterator();
while (valueIt.hasNext()) {
    Integer val = valueIt.next();
    Iterator<Integer> keyIt = mapKeys.iterator();

    while (keyIt.hasNext()) {
        Integer key = keyIt.next();
        Integer comp1 = passedMap.get(key);
        Integer comp2 = val;

        if (comp1.equals(comp2)) {
            keyIt.remove();
            sortedMap.put(key, val);
            break;
        }
    }
}
return sortedMap;
}
   public static void main(String args[])
    {
      HashMap<Integer,Integer> hs = new HashMap<Integer,Integer>();
      int a[]={3,4,3,2,3,5,4,2,2,1,2};
       int n= a.length;
       int c=0;
       for(int i=0;i<n;i++)
        {
        if(hs.containsKey(a[i]))
        {
            c=hs.get(a[i]);
            hs.put(a[i],c+1);
        }
        else
        hs.put(a[i],1);
    }
     hs=Sum_of.sortHashMapByValues(hs);
    System.out.println(hs.keySet());
      }
 }