Janki Shah
Ranch Hand
Posts: 136
how does compareTo() and compare() works in these interfaces? what algorithm do they implement?

Matthew Brown
Bartender
Posts: 4568
9
Whatever algorithm you implement in them. The interfaces just define the contract for comparing two objects - you return an integer that depends on whether the objects are in the right "order" or not.

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
do you mean Sorting algorithm? Actually there is no sorting algorithm in Comparable/Comparator instead it values the Object[relate the two object=> tells which one should come first] . The Sorting Algorithm is in Collections.sort, Arrays.sort etc...

both Collections.sort and Arrays.sort(Object[]) uses MergeSort[time complexity is O(n logn)]
<edit>
and Arrays.sort(int[]) uses QuickSort
</edit>

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Too slow

Janki Shah
Ranch Hand
Posts: 136
Seetharaman Venkatasamy wrote:do you mean Sorting algorithm? Actually there is no sorting algorithm in Comparable/Comparator instead it values the Object[relate the two object=> tells which one should come first] . The Sorting Algorithm is in Collections.sort, Arrays.sort etc...

both Collections.sort and Arrays.sort uses MergeSort[time complexity is O(n logn)]

yes that's what I ment. So, compareTo() and compare() both implements Mergesort algorithm in sorting the given object? Like how does the a.compareTo(b) really work for a List of String for example?

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Janki Shah wrote:So, compareTo() and compare() both implements Mergesort algorithm in sorting the given object? Like how does the a.compareTo(b) really work for a List of String for example?

See
matthew wrote:
The interfaces just define the contract for comparing two objects - you return an integer that depends on whether the objects are in the right "order" or not.

Paul Clapham
Sheriff
Posts: 21443
33
Janki Shah wrote:So, compareTo() and compare() both implements Mergesort algorithm in sorting the given object? Like how does the a.compareTo(b) really work for a List of String for example?

No, they don't implement any such thing. You're looking at things the wrong way around. It's Collections.sort which uses a merge-sort algorithm. And as I'm sure you know, when you are sorting things you frequently need to compare two things to see which should come first in the sorted list. So when Collections.sort needs to compare two things, it will call "thing1.compareTo(thing2)" to find out which of them should come first.

So that's how compareTo "works"... it works by being called by the sorting algorithm. And as Matthew already said, compareTo will do whatever the programmer told it to do. But all the programmer needs to be concerned with is "When is this Thing less than some other Thing, and when is it greater than some other Thing?" The programmer doesn't need to be concerned with whether its caller is a merge sort or some other kind of a sort, or whether it's a stable sort or not, or anything like that. The programmer only needs to be concerned with how to put two Things in order.

Janki Shah
Ranch Hand
Posts: 136
Thank you Metthew, Seetharaman and Paul for your explanation.
I got the point that, after comparing two things of same type you return an int value 1, -1 or 0 according to the conditions.
like this example, is my understanding correct this time?

and I can call then like this,

Matthew Brown
Bartender
Posts: 4568
9
• 1
That's right, yes. There's a couple of improvements you can make, though. Comparator is a generic interface - you should use the generic type. You avoid the casting and you get better type safety. Secondly, the Double class has a method for comparing two doubles. So:

Also remember, it doesn't have to be +/- 1 exactly, it can be any positive or negative integers. So when the quantities you're comparing are integers you can just subtract them. If getSalary() returned an int, the above example could be changed to:

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Cool .
Janki Shah wrote:

Or, simply

Matthew Brown
Bartender
Posts: 4568
9
• 1
Seetharaman Venkatasamy wrote:Or, simply

Dangerous with doubles!

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Matthew beaten me this time too

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Matthew Brown wrote:
Dangerous with doubles!

Agree

Janki Shah
Ranch Hand
Posts: 136
Matthew Brown wrote:That's right, yes. There's a couple of improvements you can make, though. Comparator is a generic interface - you should use the generic type. You avoid the casting and you get better type safety. Secondly, the Double class has a method for comparing two doubles. So:

Also remember, it doesn't have to be +/- 1 exactly, it can be any positive or negative integers. So when the quantities you're comparing are integers you can just subtract them. If getSalary() returned an int, the above example could be changed to:

All points are noted. Thank you very much for the great explanation.

Arvind Darwin
Greenhorn
Posts: 10
Matthew Brown wrote:
Seetharaman Venkatasamy wrote:Or, simply

Dangerous with doubles!

Can you please explain, why is this dangerous with doubles?
Is it because return type is int and result of statement is double - which could lead to loss of precision?

Matthew Brown
Bartender
Posts: 4568
9
Arvind Darwin wrote:Can you please explain, why is this dangerous with doubles?
Is it because return type is int and result of statement is double - which could lead to loss of precision?

Loss of precision, yes, but that leads to a particular problem here.

Try this. Which is bigger? 1.2 or 0.5? Applying that simple comparator you'd get 1.2 - 0.5 = 0.7. Now you want to cast that to an int...which will truncate it, and the compare method will return 0. So any code using the comparator will think the values are equal.

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Matthew given much better explanation

 Consider Paul's rocket mass heater.