Sort elements by frequency

Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.

Examples:

Input:  arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}

Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}

 Input 5  2  2  8  5  6  8  8

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

  Now construct the 2D array as
  Index, Count
  1,      2
  0,      2
  5,      1
  3,      3

  Sort by count (consider indexes in case of tie)
  3, 3
  0, 2
  1, 2
  5, 1
  
  Print the elements using indexes in the above 2D array.

=================================================

JAVA IMPLEMENTATION

=================================================

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Set;

class Element{

int value;

int index;

int count;

public Element(int value, int index, int count){

this.value = value;

this.index = index;

this.count = count;

}

}

public class SortElementByFrequency {

public static void main(String[] args) {

int array[] = {2, 5, 2, 6, -1, 999999, 5, 8, 8, 8};

int index = 0;

Map<Integer, Element> map = new HashMap<Integer , Element>();

for (int value : array) {

Element element = new Element(value, index, 1);

index++;

if(map.get(element.value) != null){

Element newelement = map.get(element.value);

newelement.count += 1;

map.put(element.value, newelement);

}else{

map.put(element.value, element);

}

}

Set<Integer> keys = map.keySet();

List<Element> list = new ArrayList<Element>();

for (Integer key : keys) {

list.add(map.get(key));

}

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

@Override

public int compare(Element e1, Element e2) {

// TODO Auto-generated method stub

if(e2.count-e1.count != 0){

return e2.count-e1.count;

}else{

return e1.index-e2.index;

}

}

});

for (Element element : list) {

int count = element.count;

while(count > 0){

System.out.print(element.value + "  ");

count--;

}

}

}

}