3

I was so confused about comparator and Collections.sort() in Java. I don't understand the order induced by the comparator. I don't clear about which number the compare function should return to get the sorting direction. I also don't know how Collections will use that compare result to sort the input data. Should I learn them by heart? Is there anything easier to understand them? Can anybody explain it for me? Thanks. 

public int compare(Obj a, Obj b){ 
    if(a.age > b.age) return 1; 
    if(a.age < b.age) return -1;
    else              return 0;
}

Update

After received some explanations from some friendly Software Engineer, I understood that the comparator define the order of elements in a Collections. For example, when compare a and b, if the comparator return -1 then a should be put before b in the list.

Minh Tri Le
  • 350
  • 2
  • 12
  • 2
    See https://stackoverflow.com/questions/2839137/how-to-use-comparator-in-java-to-sort – Raedwald Dec 22 '18 at 09:36
  • 1
    My mnemonic is: return `a.age - b.age`, putting `a` and `b` in the same order in the subtraction as they are in the parameter list, then it will give the correct result for sorting into increasing order. If `age` is an `int` with values from 0 through 140, this is correct. It’s not correct for arbitrary `int` values because of `int` overflow and underflow, but my mnemonic works well in all cases to figure out when to return a negative value and when to return a positive one (they need not be 1 and -1). – Ole V.V. Dec 22 '18 at 10:11

3 Answers3

4

Key thing to remember is if comparison returns positive value ( >0) swap happens. Otherwise not during sorting algorithm.

Example:

4(a) 2(b) 6

For ascending order:

a > b (4 > 2) return 1 (swap requires between a and b i.e place 2 4 6)

For descending order:

a > b ( 2 > 4 ) return -1 (swap not needed between a and b i.e place 4 2 6, because it is already in order).

This logic implemented under sorting algorithm, So, just think if a and b are already in order as you expected then return -1 otherwise return 1.

vikash singh
  • 1,479
  • 1
  • 19
  • 29
Bharatesha M
  • 41
  • 4
1

To sort a set of items, we should be able to compare each pair of items in that set and say which is "bigger" and which is "smaller".

Imagine you are given the task of sorting below numbers manually.

4, 2, 7, 8, 3

How would you use your mind to achieve this task? You would have to look at pairs of numbers and compare them and then figure out which is the smallest number to place at the begging.

Similarly, to achieve a sorting task, a computer needs to compare pairs of items and say which is "bigger" and which is "smaller".

So, the comparator object we write is "the definition" of which is bigger and which is smaller. When we sort numbers, this definition should say which is bigger and which is smaller. When we sort strings, this definition should say which letter in the alphabet comes first and which letter comes after.

Prasad Karunagoda
  • 2,048
  • 2
  • 12
  • 16
  • I understand that, I just don't understand why if the comparator return -1 then the order will be ascending. – Minh Tri Le Dec 22 '18 at 09:36
  • Yes, the comparator defines the "order". It doesn't say ascending or descending. If `compareTo(object1, object2)` returns `-1`, then object1 comes first and object2 comes second in the order. – Prasad Karunagoda Dec 22 '18 at 09:46
0

Step 1

One way to simplify and correlate this could be that your code:

public int compare(Obj a, Obj b){ 
    if(a.age > b.age) return 1; 
    if(a.age < b.age) return -1;
    else              return 0;
}

would be represented as following(given age is int variable)

public int compare(Obj a, Obj b) {
    return Integer.compare(a.getAge(), b.getAge());
}

where Integer.compare internally does the same logic as you were doing previously:

return (x < y) ? -1 : ((x == y) ? 0 : 1)

Step 2

Now this can further be represented using a comparator as:

Comparator<Obj> ageComparator = Comparator.comparingInt(Obj::getAge);

which Comparator.comparingInt internally performs

return (Comparator<T> & Serializable)
        (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));

Hence the order eventually induced by all these three forms would be same when for example you would call

objList.sort(ageComparator);

Comparable's compareTo method can elaborate more on the part of comparison

Compares this object with the specified object for order.  Returns a
negative integer, zero, or a positive integer as this object is less
than, equal to, or greater than the specified object.

and hence that is considered to be the natural ordering of the Obj when you override the compareTo extending to a Comparable<Obj>.

Naman
  • 27,789
  • 26
  • 218
  • 353