aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Sorting with Comparable 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 "Sorting with Comparable" Watch "Sorting with Comparable" New topic
Author

Sorting with Comparable

jibs parap
Ranch Hand

Joined: Dec 07, 2004
Posts: 134



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.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42263
    
  64
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.


Ping & DNS - my free Android networking tools app
jibs parap
Ranch Hand

Joined: Dec 07, 2004
Posts: 134
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?
Abdullah Mamun
Ranch Hand

Joined: Mar 19, 2007
Posts: 99

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...


MooN
jibs parap
Ranch Hand

Joined: Dec 07, 2004
Posts: 134
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

Joined: Dec 07, 2004
Posts: 134
a little error in the earlier statement:
please read as: ...ascending order should be [b, a]...
Jatin Kumar Patel
Greenhorn

Joined: Jul 30, 2007
Posts: 2
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
Marshal

Joined: Mar 22, 2005
Posts: 42263
    
  64
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

Joined: Dec 07, 2004
Posts: 134
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
Michael Ku
Ranch Hand

Joined: Apr 20, 2002
Posts: 510
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
Marshal

Joined: Mar 22, 2005
Posts: 42263
    
  64
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

Joined: Dec 07, 2004
Posts: 134
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

Joined: Mar 19, 2007
Posts: 99

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

Joined: Dec 07, 2004
Posts: 134
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

Joined: Mar 19, 2007
Posts: 99

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

Joined: Dec 07, 2004
Posts: 134
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

Joined: Mar 19, 2007
Posts: 99

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

Joined: Dec 07, 2004
Posts: 134
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].
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Sorting with Comparable