• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Sorting with Comparable

 
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator



Above is the code with some debug.
if you change this line, return m.name.compareTo(name) to return name.compareTo(m.name) the resulting output differs to [goban, powerbook, skis]. I expected both to return the same list. Please explain.
 
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Form the javadocs of Comparable: "This interface imposes a total ordering on the objects of each class that implements it."

So there's an ordering involved - which means that comparing a to b can't yield the same result as comparing b to a: it yields the reverse order. Ordering is not commutative.

So the code that you posted has it exactly the wrong way around - unless you wanted a reverse ordering.
 
jibs parap
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
when 'a' is compared to 'b' if it returns a +ve int, that means a>b, then
when 'b' is compared to 'a' it should return -ve int, again that means b<a, so the resultant order should be same? If yes, how can the order be reversed?
 
Ranch Hand
Posts: 99
Mac Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The javadoc says compareTo(T o) method "Compares this object with the specified object for order". This is always true for any implementation whether 'a' is compared to 'b' or 'b' is compared to 'a'.

Now, in case of the implementation 'a' is compared to 'b', returns +ve whereas for the implementation 'b' is compared to 'a', returns -ve for the same compareTo(T o) call.

Isn't it seems that, the order would be reversed for the two different implementations...
 
jibs parap
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry its not clear yet!

when 'a' is compared to 'b' if it returns a +ve int, that means a>b, then when 'b' is compared to 'a' it should return -ve int, again that means b<a


a>b whether a is compared with b or b is compared with a. So the natural order which is an ascending order should be [a, b] irrespective of how its compared.

I know there is a catch somewhere...someone out there to give me a hand?
 
jibs parap
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
a little error in the earlier statement:
please read as: ...ascending order should be [b, a]...
 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Below you will find result of both cases. I've added System.out.println("this.name is "+ this.name); to simplify precisely.


Case 1: m.name.compareTo(name)

1.1
m is powerbook
m.name is powerbook
this.name is skis
m.name.compareTo(name)-3

[skis, powerbook, goban]

1.2
m is goban
m.name is goban
this.name is powerbook
m.name.compareTo(name)-9
[skis, powerbook, goban]


Case 2: name.compareTo(m.name)

2.1
m is powerbook
m.name is powerbook
this.name is skis
name.compareTo(m.name)3

(powerbook,skis,goban)

2.2
m is goban
m.name is goban
this.name is skis
name.compareTo(m.name)12

(powerbook,goban,skis)

2.3
m is goban
m.name is goban
this.name is powerbook
name.compareTo(m.name)9
[goban, powerbook, skis]

Fix one rule in your mind that "return interger value effect to obejct refered by this....."

Look at the 1.1, in this case passed object is "powerbook" and this object is skis. Resultant integer is -3 due to your reverse comparing code. -3 will treat skis is less than powerbook. so order will not change.

same will happen in 1.2 case.

Please do Case 2: as your home work..........
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by jibs parap:
a>b whether a is compared with b or b is compared with a. So the natural order which is an ascending order should be [a, b] irrespective of how its compared.



That's the wrong way of looking at it. Of course a > b, but the important thing is, what will the call a.compareTo(b) return, and what will b.compareTo(a) return?

The former should return a positive number, while the latter should return a negative one (assuming ascending ordering). By switching the order (essentially turning "this.compareTo(m)" into "m.compareTo(this)) you reversed the sorting order.

The compareTo call is essentially the JVMs way of asking "should 'a' be sorted before 'b'"? And that's a different question -with a different answer- from "should 'b' be sorted before 'a'"
 
jibs parap
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks guys.
I think the concept doesn't sink it in for me. There are more to it or Im missing somewhere.
Do you agree :
1. the sorting order is defined according to the int returned to see one object is less/more than compared to the other object.
2. then, the objects are sorted in ascending order
 
Ranch Hand
Posts: 510
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When you executing the compareTo inside of your method yo are switching the order of the objects that you are comparing.

You start out with Object A, you execute it compareTo method passing in Object B which means you are comparing Object A to Object B. When you executed your logic inside of compareTo you reversed the order of the Objects so that now you are comparing Object B to Object A. That is why the order is reversed, you told the method to reverse the order.

Think of it like this ObjectA.compareTo(ObjectB) where you want to compare the name property of each of the objects. So inside of the compareTo method

ObjectA.compareTo(ObjectB) ---> this.name.compareTo(passedObject.name)
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

1. the sorting order is defined according to the int returned to see one object is less/more than compared to the other object.


Yes, but it makes a difference whether a is compared to b, or b is compared to a. In one of the cases the result is negative, in the other it is positive, even though the underlying fact -that one number is larger than the other- is the same.

2. then, the objects are sorted in ascending order


Not necessarily - it depends on how the sort is implemented. For example, the first implementation you posted sorts in descending.
 
jibs parap
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
1. so can I say:
thisObject.compareTo(anotherObject) - always sorts in ascending order
anotherObject.compareTo(thisObject) - always sorts in descending order

2. if yes, whats the significance of int value thats retuned.
 
Abdullah Mamun
Ranch Hand
Posts: 99
Mac Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi jibs

Suppose, you have a class with two instance variables. One is of type String and another one is of type int. Now after creating more than one objects of that class, assigning values to the variables and calling sort(), in what basis you will say that the objects are sorted in ascending order or descending order?
[ August 02, 2007: Message edited by: Al Mamun ]
 
jibs parap
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So can I redefine the earlier statements as:

thisObject.compareTo(anotherObject) - always sorts in ascending order based on the int values returned
anotherObject.compareTo(thisObject) - always sorts in descending order based on the int values retuned

------------------------
PS: Any idea how this int value calculated?(just a bit curious)
 
Abdullah Mamun
Ranch Hand
Posts: 99
Mac Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The sort() method uses compareTo() to determine how the List or object array should be sorted.

Say, the sort() method will call thisObject.compareTo(anotherObject) to sort thisObject and anotherObject. If thisObject.compareTo(anotherObject) implementation returns +ve then anotherObject will come before thisObject and if thisObject.compareTo(anotherObject) implementation returns -ve then thisObject will come before anotherObject.

Following is a sample code


If you try to execute both line 1 and line 2 and see whats going on in the sort() and compareTo(), I hope you will understand why everyone is telling that sort() is dependent on compareTo() implementation.
 
jibs parap
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is your statement same as mine if you substitute 'a' for thisObject and 'b' for anotherObject?

Yours:

the sort() method will call thisObject.compareTo(anotherObject) to sort thisObject and anotherObject. If thisObject.compareTo(anotherObject) implementation returns +ve then anotherObject will come before thisObject and if thisObject.compareTo(anotherObject) implementation returns -ve then thisObject will come before anotherObject.



Mine:

when 'a' is compared to 'b' if it returns a +ve int, that means a>b, then
when 'b' is compared to 'a' it should return -ve int, again that means b<a

 
Abdullah Mamun
Ranch Hand
Posts: 99
Mac Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

when 'a' is compared to 'b' if it returns a +ve int, that means a>b, then
when 'b' is compared to 'a' it should return -ve int, again that means b<a

In my statement I was always talking about thisObject.compareTo(anotherObject) or a.compareTo(b) not about the reverse one. Because the Collections.sort() method is using the compareTo() method and handles the order of calling compareTo() method either a with b or b with a.

If a.compareTo(b) returns +ve then b will comes first
If a.compareTo(b) returns -ve then a will comes first

I don't want to say the term a>b or b>a or something like that based on the return value. Because, the implementation could also be something like the following...

[ August 03, 2007: Message edited by: Al Mamun ]
 
jibs parap
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry to make this conversation longer..pl bear with me.

Al,
If a.compareTo(b) is +ve, b.compareTo(a) is definitely -ve. i.e a>b in both cases.

My only 'argument' is this:

if the sorting is done based on the sign of the return value(provided, the code returns thisObejct.compareTo(anotherObject)), the order should always be [b, a].
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic