File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes question about comparable and comparator Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "question about comparable and comparator " Watch "question about comparable and comparator " New topic
Author

question about comparable and comparator

Janki Shah
Ranch Hand

Joined: Nov 23, 2011
Posts: 136
how does compareTo() and compare() works in these interfaces? what algorithm do they implement?
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4490
    
    8

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

Joined: Jan 28, 2008
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

Joined: Jan 28, 2008
Posts: 5575

Too slow
Janki Shah
Ranch Hand

Joined: Nov 23, 2011
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

Joined: Jan 28, 2008
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
Bartender

Joined: Oct 14, 2005
Posts: 18989
    
    8

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

Joined: Nov 23, 2011
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

Joined: Apr 06, 2010
Posts: 4490
    
    8

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

Joined: Jan 28, 2008
Posts: 5575

Cool .
Janki Shah wrote:


Or, simply
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4490
    
    8

Seetharaman Venkatasamy wrote:Or, simply

Dangerous with doubles!
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Matthew beaten me this time too
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Matthew Brown wrote:
Dangerous with doubles!

Agree
Janki Shah
Ranch Hand

Joined: Nov 23, 2011
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

Joined: Mar 05, 2012
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

Joined: Apr 06, 2010
Posts: 4490
    
    8

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

Joined: Jan 28, 2008
Posts: 5575

Matthew given much better explanation
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: question about comparable and comparator