Sort array based on count of occurrences in ascending order

Question

How can I arrange the elements in an array based on the number of occurrences of that value in ascending order in java.

This is what I've tried:

int a[]={0,0,0,1,3,3,2,1,3,5,6,0};
int b=a.length;
for(int i=0;i<b;i++) {
    for(int j=0;j<i;j++) {
        int temp;
        if( a[j]>a[i]) {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
}

for(int r=0;r<a.length;r++) {
    System.out.println(a[r]);
}

Answer 1

Using Java 8

Sort the array elements based on its frequencies

Assumptions -
1. Sort the array based on its natural occurrence in an ascending order
2. If two numbers having same frequencies then sort them based on natural number precedence

Example: - [ 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5]
Output: -    [ 5, 4, 4, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1, 1]

Solution: -
1. Create a HashMap which stores the array elements and its occurrences
2. Put hashmap into a List where we can apply sorting based on its frequencies using a customized comparator
3. Object Comparision is Java: -
  if Obj1 is less then Obj2 then return -1
  if Obj1 is equal to Obj2 then return 0
  if Obj1 is greater then Obj2 then return +1
4. In our case, if two numbers have the same frequences then we should put the number which has natural precedence in the output
  Ex: - if above example, number 2 and 3 occurred 3 times hence 2 should come first

public static void sortTheArrayByFrequency(int[] array){
    Map<Integer, Integer> map = new HashMap<>();

    //put array elements based on its frequncies
    for(int i : array){
        map.put(i, map.getOrDefault(i,0)+1);  
    }

    //Put the hashmap into a list where we use customized comparator
    List<Map.Entry<Integer, Integer>> list = new ArrayList<>();
    for(Map.Entry<Integer, Integer> e : map.entrySet()){
        list.add(e);
    }

    // list looks like [1=5, 2=3, 3=3, 4=2, 5=1]

    Collections.sort(list, (a, b) -> {
        // if its ouccrances are same then sort natually
        //else sort based on freqncies
        if(a.getValue() == b.getValue())
            return a.getKey() - b.getKey();
        else
            return a.getValue() - b.getValue();
    });

    // list looks like [5=1, 4=2, 2=3, 3=3, 1=5]

    for(Map.Entry<Integer, Integer> e : list){
        int num = e.getValue();
        while(num!=0){
            System.out.print(e.getKey()+ " ");
            num--;
        }
    }
}

Output:-
5 4 4 2 2 2 3 3 3 1 1 1 1 1

Answer 2

Here is an efficient way to do it using TreeMap.

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class FrequencySort {
    public static void main(String[] args) {
        int[] ar = new int[] {5,2,8,8,5,5,8,1,9,0,1,1,0,1};

        Map<Integer,Integer> numbers = new HashMap<>();

        for(int number : ar) {
            if(numbers.containsKey(number)) {
                Integer  count = numbers.get(number);
                numbers.put(number, ++count);
            } else {
                numbers.put(number,1);
            }
        }

        final class FrequencyComparator implements Comparator<Integer> {
            Map<Integer,Integer> refMap;
            public FrequencyComparator(Map<Integer,Integer> base) {
                this.refMap = base;
            }

            @Override
            public int compare(Integer k1, Integer k2) {
                Integer val1 = refMap.get(k1);
                Integer val2 = refMap.get(k2);

                int num = val1.compareTo(val2)  ;
                // if frequencies are same then compare number itself
                return  num == 0 ? k1.compareTo(k2)   : num;
            }
        }

        FrequencyComparator comp = new FrequencyComparator(numbers);
        TreeMap<Integer,Integer> sortedMap = new TreeMap<Integer,Integer>(comp);
        sortedMap.putAll(numbers);
        for(Integer i : sortedMap.keySet()) {
            int frequencey = sortedMap.get(i);
            for(int count  = 1 ; count <= frequencey ; count++) {
                System.out.print(i + " " );
            }
        }
    }
}