Monday 25 August 2014

Sort elements by frequency

Sort the elements of an array by number of times they repeated in ascending order.

For Example
let array 'a' has 5, 4, 3, 2, 1, 0, 5, 3, 2, 4, 1, 2, 3, 5

Then the output should be like below.
0 1 1 4 4 2 2 2 3 3 3 5 5 5

Procedure:
Step 1: Find frequency count of each element in the array and construct map.

For the above example
Value Frequency
0 1
1 2
2 3
3 3
4 2
5 3

Step 2: You got the frequency for each element in the array, now apply sorting logic based on the frequency.

import java.util.*;

public class SortByFrequency {
    
    static void sortByFreq(int a[]){
        Map<Integer, Integer> map = new TreeMap<> ();
        
       /* Logic to place the elements to Map */
       for(int i=0; i<a.length; i++){
           if(map.get(a[i]) == null){
               map.put(a[i], 1);
            }
           else{
               int frequency = map.get(a[i]);
               map.put(a[i], frequency+1);
           }
       }
       
       //System.out.println(map);
       
       List list = new LinkedList(map.entrySet());
       
       /* Sort the list elements based on frequency */
       Collections.sort(list, new Comparator() {
            @Override
            public int compare(Object obj1, Object obj2) {
               return ((Comparable) ((Map.Entry) (obj1)).getValue())
                  .compareTo(((Map.Entry) (obj2)).getValue());
            }
       });
       
       int count=0;
       
       /* Place the elements in to the array based on frequency */
       for (Iterator it = list.iterator(); it.hasNext();) {
            Map.Entry entry = (Map.Entry) it.next();
            
            int key = (int)entry.getKey();
            int val = (int)entry.getValue();
            
            for(int i=0; i < val; i++){
                a[count] = key;
                count++;
            }            
       } 
    }
    
    public static void main(String args[]){
        int a[] = {5,4,3,2,1,0,5,3,2,4,1,2,3,5};
        
        System.out.println("Before Sorting");
        for(int i=0; i<a.length; i++){
            System.out.print(a[i] +" ");
        }
        
        sortByFreq(a);
        
        System.out.println("\nAfter Sorting");
        for(int i=0; i<a.length; i++){
            System.out.print(a[i] +" ");
        }
    }
}

Output
Before Sorting
5 4 3 2 1 0 5 3 2 4 1 2 3 5 
After Sorting
0 1 1 4 4 2 2 2 3 3 3 5 5 





Prevoius                                                 Next                                                 Home

No comments:

Post a Comment