This week's book giveaway is in the Other Languages forum.
We're giving away four copies of Functional Reactive Programming and have Stephen Blackheath and Anthony Jones on-line!
See this thread for details.
Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

question about comparable and comparator

 
Janki Shah
Ranch Hand
Posts: 136
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
how does compareTo() and compare() works in these interfaces? what algorithm do they implement?
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Too slow
 
Janki Shah
Ranch Hand
Posts: 136
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 21416
33
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Cool .
Janki Shah wrote:


Or, simply
 
Matthew Brown
Bartender
Posts: 4568
9
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Seetharaman Venkatasamy wrote:Or, simply

Dangerous with doubles!
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew beaten me this time too
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew Brown wrote:
Dangerous with doubles!

Agree
 
Janki Shah
Ranch Hand
Posts: 136
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew given much better explanation
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic