CODEWITHSUNDEEP
javalistsorting
John P.
John P.

Reputation: 215

Sorting an arraylist according to number of occurences of similar elements

I have an ArrayList containing {2,2,1,1,1,5,4,4,4,4,4} and I want to sort it according to number of occurrences of each element. So it will give {4,4,4,4,4,1,1,1,2,2,5}. Where do I start?

import java.util.*;

public class SortingL{

  public static void main(String[] args){

    ArrayList<Integer> list = new ArrayList<Integer>();

    Integer[] al = new Integer[] {2,2,1,1,1,5,4,4,4,4,4};
    list.addAll(Arrays.asList(al));

    sortL(list);

  }

  public static ArrayList<Integer> sortL(ArrayList<Integer> list){


    return list;
  }
}

Upvotes: 2

Views: 3140

Answers (3)

Jigar Joshi
Jigar Joshi

Reputation: 240948

You can do it with O(N) (with little tradeoff of memory space. )

  1. List item
  2. Create a hashmap
  3. Iterate through your input elements and maintain count of each element in hashmap
  4. Now iterate through Map's keys and bucket numbers by frequencies
  5. Now iterate bucket in reverse order

Code:

public List<Integer> frequencyBasedSort(int[] nums, int k) {
    List<Integer>[] bucket = new List[nums.length + 1];
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int n : nums) {
        freqMap.put(n, freqMap.getOrDefault(n, 0) + 1);
    }
    for (int key : freqMap.keySet()) {
        int frequency = freqMap.get(key);
        if (bucket[frequency] == null) {
            bucket[frequency] = new ArrayList<>();
        }
        bucket[frequency].add(key);
    }
    List<Integer> res = new ArrayList<>();
    for (int i = bucket.length - 1; i >= 0; i--) {
        if (bucket[i] != null) {
            res.addAll(bucket[i]);
        }
    }
    return res;
}

Upvotes: 1

Andreas
Andreas

Reputation: 159165

For best performance, first build a Map of value to count of values. Then sort that by count, and re-build the array.

The effect will be that different values which occur the same number of times will be consolidated. You'd probably want to specify secondary order, then they are consistently sorted.

Example:

public static void main(String[] args) {
    ArrayList<Integer> input = new ArrayList<>(Arrays.asList(2,2,1,1,1,5,4,4,4,4,4));
    ArrayList<Integer> sorted = sortL(input);
    System.out.println(sorted); // prints: [4, 4, 4, 4, 4, 1, 1, 1, 2, 2, 5]
}
public static <V extends Comparable<V>> ArrayList<V> sortL(List<V> input) {
    Map<V, ValueCount<V>> map = new HashMap<>();
    for (V value : input)
        map.computeIfAbsent(value, ValueCount<V>::new).count++;
    @SuppressWarnings("unchecked")
    ValueCount<V>[] arr = map.values().toArray(new ValueCount[map.size()]);
    Arrays.sort(arr);
    ArrayList<V> sorted = new ArrayList<>(input.size());
    for (ValueCount<V> vc : arr)
        for (int i = 0; i < vc.count; i++)
            sorted.add(vc.value);
    return sorted;
}
private static final class ValueCount<V extends Comparable<V>> implements Comparable<ValueCount<V>> {
    final V value;
    int count;
    ValueCount(V value) {
        this.value = value;
    }
    @Override
    public int compareTo(ValueCount<V> that) {
        int cmp = Integer.compare(that.count, this.count); // descending
        if (cmp == 0)
            cmp = that.value.compareTo(this.value); // descending
        return cmp;
    }
}

Upvotes: 3

Jacob G.
Jacob G.

Reputation: 29720

One solution would be to use Collections#frequency:

List<Integer> list = Arrays.asList(2, 2, 1, 1, 1, 5, 4, 4, 4, 4, 4);

list.sort(Comparator.comparing(i -> Collections.frequency(list, i)).reversed());

System.out.println(list);

This will output the expected result:

[4, 4, 4, 4, 4, 1, 1, 1, 2, 2, 5]

Upvotes: 6

Related Questions