CODEWITHSUNDEEP
javacomparator
Rufus7
Rufus7

Reputation: 115

Java, how to sort char alphabetically in Comparator

I am trying to built a maxheap of characters. First sort by frequency, if frequency is same, then sort alphabetically.

Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < n; i++) {
     char c = s.charAt(i);
     map.put(c, map.getOrDefault(c, 0) + 1);
}

Queue<Character> pq = new PriorityQueue<>(new Comparator<Character>(){
  @Override
  public int compare(Character c1, Character c2){
   if(map.get(c1) == map.get(c2)){
     return c1 < c2 ? -1 : (c1 == c2 ? 0 : 1);
     //return (char)c1 - (char)c2; same output
   }
   return map.get(c2) - map.get(c1);
  }
});

for(char key : map.keySet()){
   pq.offer(key);
   System.out.println(key + " has freq " + map.get(key));
}

while(!pq.isEmpty()) {
     System.out.print(pq.poll() + " ");
}

I put 26 letters into this maxheap, and each letter has same frequency 5000.

But the output order is 'a', 'z', 'y', 'x'...., 'c', 'b'.
enter image description here

when frequency of each char is 5, the order is correct. enter image description here

I don't understand why the output with frequency 5000 is like this. How can I get a right order?

Upvotes: 0

Views: 627

Answers (3)

Holger
Holger

Reputation: 298173

You are comparing two Integer instances via == with the if(map.get(c1) == map.get(c2)) statement. The reason why it works when the frequency is five, is that there is a mandatory caching for autoboxing values in the -128…+127 range. When the frequency is 5000, the identity of the Integer objects is unspecified and equal objects may have different identities.

One fix would be to use equals instead. The other is to stop implementing Comparator manually and use the factory methods. Together with other improvements, your code simplifies to

Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < n; i++) {
     map.merge(s.charAt(i), 1, Integer::sum);
}

Queue<Character> pq = new PriorityQueue<>(
    Comparator.<Character>comparingInt(map::get).reversed()
        .thenComparing(Comparator.naturalOrder())
);

map.forEach((key, freq) -> {
   pq.offer(key);
   System.out.println(key + " has freq " + freq);
});

while(!pq.isEmpty()) {
     System.out.print(pq.poll() + " ");
}

Upvotes: 1

OneCricketeer
OneCricketeer

Reputation: 191728

Given that all frequencies are the same, your if statement is wrong. You could use built-in methods to compare the objects and return the results 

Integer f1 = map.get(c1);
Integer f2 = map.get(c2);
int x = f1.compareTo(f2)
if(x == 0){
    return Character.compare(c1, c2);
}
return x;

Upvotes: 3

Muzamil Mehmood
Muzamil Mehmood

Reputation: 44

you can compare two objects with .equals() method. it will return a Boolean value. if you want to hard code comparison then assign a integer value to each alphabet(total 26 variables) and compare their integer value and you'll know which one to place where.

Upvotes: 0

Related Questions