Sort Elements By Frequency

Problem: You are given an array. You have to sort the array elements in decreasing order of their frequency.

eg. [2,3,4,2,8,1,1,2]
Output: [2 2 2 1 1 3 4 8]

Solution:

Method 1 (Use Sorting)

1) Use quick sort algorithm to sort the elements O(nlogn)
2) Scan the sorted array and construct a 2D array of element and count O(n).
3) Sort the 2D array according to count O(nlogn).

Input 2,3,4,2,8,1,1,2

After sorting we get
2 2 2 1 1 3 4 8

Now construct the 2D array as
2, 3
1, 2
3, 1
4, 1
8, 1

Sort by count
8, 3
2, 2
5, 2
6, 1

If we modify the input to 2 2 2 1 1 1 3 4 8, then we should get 2 2 2 1 1 1 3 4 8 and not 1 1 1 2 2 2 3 4 8.
To handle this, we should use indexes instead of the actual element, if two counts are same then we should first process(or print) the element with lower index.

Input 2 2 2 1 1 1 3 4 8

After sorting we get
Element 1 1 1 2 2 2 3 4 8
Index 3 4 5 1 2 3 6 7 8

Now construct the 2D array as
Index, Count
3, 3
1, 3
6, 1
7, 1
8, 1
Sort by count (consider indexes in case of tie)
Index, Count
3, 3
1, 3
6, 1
7, 1
8, 1

Print the elements using indexes in the above 2D array.
2 2 2 1 1 1 3 4 8

Method 2 (Use Hash)

Using a hashing mechanism, we can store the elements (also first index) and their counts in a hash. Finally, sort the hash elements according to their counts.

If you have any better approach, Please write or comment below.

5 Thoughts on “Sort Elements By Frequency

  1. Ayush Pandey on December 20, 2013 at 1:07 pm said:

    after sorting the array how would you get to know which value corresponds to which element of original array…i mean our array is :2,3,4,2,8,1,1,2 after applying operations we get array as 0,2,3,1,0,0,0,1
    now if we sort the array how we would able to map which value corresponds to which element?

    • Ranveer Singh on March 1, 2014 at 3:38 am said:

      To solve this problem. we will not sort the last array, we simply start printing value of the array from minimum frequency value 1 to maximum frequency value

  2. Stefanos on April 29, 2014 at 2:49 am said:

    import java.util.Arrays;
    import java.util.Map;
    import java.util.TreeMap;

    public class FrequencySorter
    {
    private static int[] a;

    public static void print()
    {
    for (int i : a)
    {
    System.out.print(i + ” “);
    }
    }

    public static int[] sort()
    {
    Arrays.sort(a);

    Map m = new TreeMap();

    int counter = 0;
    int index = 0;
    int previous = a[index];
    for (int i : a)
    {
    if (i == previous)
    {
    counter++;
    }
    else
    {
    m.put(counter, previous);
    counter = 0;
    }
    previous = i;
    }

    int[] b = new int[m.size()];

    int n = m.size()-1;
    for (Integer i : m.values())
    {
    b[n] = i;
    n–;
    }

    return b;

    }

    public static void main(String[] args)
    {
    int[] b = {1,2,2,1,3,3,3,3,3,4,5};

    a = b;

    int[] s = sort();

    print();

    System.out.println();

    for (int i : s)
    {
    System.out.print(i + ” “);
    }

    }

    }

  3. I could do that in O(N) with O(N) space. Basically, what I did were:
    1. Put key and its frequency (as value) in a hash map
    2. Put all of the entries in a tree map which a custom Comparator. In this comparator, we first compare frequency and also the key to determine the order in the tree map.
    3. Iterator through the Tree map and build the output ( or you can put it back to an array output)

    Below is the code in java:

    public static void printOutFrequencySort(int[] a) {
    //Print input.
    for( int i = 0; i < a.length; ++i) {
    System.out.print( a[i] + " ");
    }
    System.out.println();

    Map counting = new HashMap();
    Comparator cp = new KeyValueComparator(counting);
    TreeMap treeMap = new TreeMap(cp);

    for( int i = 0; i < a.length; ++i) {
    Integer value = counting.get(a[i]);
    if( value == null) {
    counting.put(a[i], new Integer(1));
    } else {
    counting.put( a[i], new Integer(value + 1));
    }
    }

    System.out.println( counting);
    treeMap.putAll(counting);
    System.out.println( treeMap );

    // print output
    for( Map.Entry entry : treeMap.entrySet()) {
    Integer value = entry.getKey();
    Integer frequency = entry.getValue();
    for( int i = 0; i < frequency.intValue(); ++i) {
    System.out.print(value + " ");
    }
    }

    System.out.println();

    }

    static class KeyValueComparator implements Comparator {

    Map map;
    KeyValueComparator(Map map) {
    this.map = map;
    }

    @Override
    public int compare(Integer k1, Integer k2) {
    Integer v1 = map.get(k1);
    Integer v2 = map.get(k2);
    if( v1 > v2) {
    return -1;
    } else if ( v1 == v2) {
    return k1 < k2 ? -1 : 1;
    }

    return 1;
    }
    }

  4. Vijaya on March 13, 2015 at 6:00 am said:

    //get the element count
    //sort the map according to key Values
    //print the elements

    public class SortElementsByFrequency
    {
    static LinkedHashMap hm = new LinkedHashMap();
    public static void main(String[] args)
    {
    //int[] a = {2,3,4,2,8,1,1,2};
    int[] a = {2,2,2,1,1,1,3,4,8};
    frequencyCount(a);

    //Adding entrySet to LinkedList

    List<Map.Entry> list = new LinkedList<Map.Entry>(hm.entrySet());

    Collections.sort(list,new Comparator<Map.Entry>()
    {

    @Override
    public int compare(Entry arg0,
    Entry arg1) {

    return arg1.getValue()-arg0.getValue();
    }

    });

    for(Map.Entry i:list)
    {
    for(int j=0;j<i.getValue();j++)
    {
    System.out.print(i.getKey()+" ");
    }
    System.out.println();
    }

    }

    public static void frequencyCount(int[] a)
    {
    for(int i=0;i<a.length;i++)
    {
    if(hm.containsKey(a[i]))
    hm.put(a[i],hm.get(a[i])+1);
    else
    hm.put(a[i], 1);

    }

    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation