Sort elements by frequency

// Java program to sort elements by frequency. If two
// elements have same count, then put the elements that
// appears first Importing required classes
import java.util.*;

class ele {
  int count, index, val;

}
// Used for sorting by value
class mycomp implements Comparator<ele> {
  public int compare(ele a, ele b)
  {
    return (a.val - b.val);
  }
}

// Used for sorting by frequency. And if frequency is same,
// then by appearance
class mycomp2 implements Comparator<ele> {
  public int compare(ele a, ele b)
  {
    if (a.count != b.count)
      return (a.count - b.count);
    return (b.index - a.index);
  }
}

class GFG {

  static void sortByFrequency(int[] arr, int n)
  {
    ArrayList<ele> element = new ArrayList<ele>();
    // ele[] element = new ele[n];
    for (int i = 0; i < n; i++) {

      element.add(new ele());
      // Fill Indexes
      element.get(i).index = i;

      // Initialize counts as 0
      element.get(i).count = 0;

      // Fill values in structure
      // elements
      element.get(i).val = arr[i];
    }

    /* Sort the structure elements according to value,
           we used stable sort so relative order is
           maintained.
         */
    Collections.sort(element, new mycomp());

    /* initialize count of first element as 1 */
    element.get(0).count = 1;

    /* Count occurrences of remaining elements */
    for (int i = 1; i < n; i++) {

      if (element.get(i).val == element.get(i - 1).val) {
        element.get(i).count += element.get(i - 1).count + 1;

        /* Set count of previous element as -1, we
                   are doing this because we'll again sort
                   on the basis of counts (if counts are
                   equal than on the basis of index)*/
        element.get(i - 1).count = -1;

        /* Retain the first index (Remember first
                   index is always present in the first
                   duplicate we used stable sort. */
        element.get(i).index = element.get(i - 1).index;
      }

      /* Else If previous element is not equal to
              current so set the count to 1 */
      else
        element.get(i).count = 1;
    }

    /* Now we have counts and first index for each
           element so now sort on the basis of count and in
           case of tie use index to sort.*/
    Collections.sort(element, new mycomp2());
    for (int i = n - 1, index = 0; i >= 0; i--){
      if (element.get(i).count != -1)
      {
        for (int j = 0; j < element.get(i).count;j++)
          arr[index++] = element.get(i).val;
      }
    }
  }

  // Driver code
  public static void main(String[] args)
  {
    int[] arr = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };
    int n = arr.length;

    // Function call
    sortByFrequency(arr,     n);

    for (int i = 0; i < n; i++)
      System.out.print(arr[i] + " ");
  }
}

// This code is contributed by Abhijeet Kumar(abhijeet19403)

// Java program for above approach
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
class GFG {

    static Integer[] arr
        = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };

    // Driver Code
    public static void main(String[] args)
    {
        List<Integer> list = Arrays.asList(arr);

        // Function call
        sortBasedOnFrequencyAndValue(list);
    }

    // Compare Function
    public static void
    sortBasedOnFrequencyAndValue(List<Integer> list)
    {
        int n = arr.length;
        final HashMap<Integer, Integer> mapCount
            = new HashMap<Integer, Integer>();
        final HashMap<Integer, Integer> mapIndex
            = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            if (mapCount.containsKey(arr[i])) {
                mapCount.put(arr[i],
                             mapCount.get(arr[i]) + 1);
            }
            else {
                mapCount.put(
                    arr[i],
                    1); // Map to capture Count of elements
                mapIndex.put(arr[i],
                             i); // Map to capture 1st
                                 // occurrence of elements
            }
        }

        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer n1, Integer n2)
            {
                int freq1 = mapCount.get(n1);
                int freq2 = mapCount.get(n2);
                if (freq1 != freq2) {
                    return freq2 - freq1;
                }
                else {
                    return mapIndex.get(n1)
                        - mapIndex.get(
                            n2); // Elements with Lesser
                                 // Index gets Higher
                                 // Priority
                }
            }
        });
        System.out.println(list);
    }
}

static class tree {
    int element;
    int first_index; /*To handle ties in counts*/
    int count;
}
tree BST = new tree();

// This code is contributed by gauravrajput1

import java.util.*;

class Compare
  implements Comparator<Map.Entry<Integer, Integer> > {
  public int compare(Map.Entry<Integer, Integer> a,
                     Map.Entry<Integer, Integer> b)
  {
    // b is at top and a is at bottom - have that in
    // mind
    if (a.getValue() == b.getValue()) // when freq same
      return a.getKey().compareTo(
      b.getKey()); // smaller val stays at top
    return b.getValue().compareTo(
      a.getValue()); // higher freq stays at top
  }
}

class Main {
  static void solve(List<Integer> arr)
  {
    int N = arr.size();
    Map<Integer, Integer> mpp
      = new HashMap<>(); // val, freq
    for (int a : arr) {
      mpp.put(a, mpp.getOrDefault(a, 0) + 1);
    }
    // max heap - as max wise freq elements is what
    // needed
    PriorityQueue<Map.Entry<Integer, Integer> > maxH
      = new PriorityQueue<>(new Compare());

    for (Map.Entry<Integer, Integer> m :
         mpp.entrySet()) {
      maxH.add(m); // freq, val
    }
    // now the max freq is at TOP of MAX heap

    int i = 0; // to maintain index to copy
    while (maxH.size() > 0) {
      int val = maxH.peek().getKey(); // val
      int freq = maxH.peek().getValue(); // freq

      while (freq-- > 0) {
        // freq - those many times make a copy
        arr.set(i, val);
        i++;
      }
      maxH.poll(); // heapify happens and next top
      // freq ele goes up
    }
  }

  public static void main(String[] args)
  {
    List<Integer> arr
      = Arrays.asList(2, 5, 2, 8, 5, 6, 8, 8);
    int n = arr.size();

    // Function call
    solve(arr);

    for (int i = 0; i < n; i++)
      System.out.print(arr.get(i) + " ");
    System.out.println();
  }
}

// This code is contributed by divyansh2212

// Java code for the above approach
import java.util.Arrays;

public class GFG {
    static class ele {
        public int val;
        public int count;
    }

    static void swap(ele[] arr, int i, int j) {
        ele temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static int partition(ele[] arr, int low, int high) {
        ele pivot = arr[high];
        int i = low - 1;

        for (int j = low; j <= high - 1; j++) {
            if (arr[j].count < pivot.count || (arr[j].count == pivot.count && arr[j].val > pivot.val)) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    static void quicksort(ele[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quicksort(arr, low, pi - 1);
            quicksort(arr, pi + 1, high);
        }
    }

    static void sortByFrequency(int[] arr, int n) {
        ele[] element = new ele[n];
        for (int i = 0; i < n; i++) {
            element[i] = new ele();
            element[i].val = arr[i];
            element[i].count = 0;
        }

        for (int i = 0; i < n; i++) {
            int j;
            for (j = 0; j < i; j++)
                if (arr[i] == arr[j])
                    break;

            if (i == j)
                element[i].count++;
            else
                element[j].count++;
        }

        quicksort(element, 0, n - 1);

        for (int i = n - 1, index = 0; i >= 0; i--) {
            for (int j = 0; j < element[i].count; j++)
                arr[index++] = element[i].val;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 2, 5, 2, 8, 5, 6, 8, 8 };
        int n = arr.length;

        sortByFrequency(arr, n);

        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}

// This code is contributed by Pushpesh Raj