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 Need help in understanding how Comparable and Comparator works ? 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 "Need help in understanding how Comparable and Comparator works ?" Watch "Need help in understanding how Comparable and Comparator works ?" New topic
Author

Need help in understanding how Comparable and Comparator works ?

gurpeet singh
Ranch Hand

Joined: Apr 04, 2012
Posts: 923
    
    1

Hi guys, I'm preparing for SCJP 6 from kb book. I'm having really hard time in understanding comparable and comparator interface. Following is the code listing from KB book Page no. 573

CODE LISTING



Further the book says "Now, when we invoke Collections.sort(dvdList); we get our arraylist sorted by title.

the difficulty i'm facing is in understanding the flow of the program. what happens when we do Collections.sort(dvdList) ? how many times does compareTo() gets called and from where compareTo(DVDInfo d) receives its arguments ?


OCPJP 6(100 %) OCEWCD 6(91 %) OCPJBCD(93%)
Helen Ma
Ranch Hand

Joined: Nov 01, 2011
Posts: 451
The Collections.sort method has an algorithm which calls the compareTo method of each DVDInfo instance.

Let's look at scenarios of sorting two DVDInfo instance in ascending order in this case:

If the compareTo method returns 1 (one string (this.title) is bigger than the next string (the string from d.getTitle()) in the unsorted list) , then Collections.sort will swap two DVDInfo instances in ascending order.
If the compareTo method returns 0 (the strings are the equal meaningfully), then sort will not do anything on the two objects.
If the compareTo method returns -1 (one string is smaller than the next string in the unsorted list), then the sort method will not swap them.


First digest this post.

If you want to know more about sorting in descending order, let us know then.


Md. Minhajur Rahman
Ranch Hand

Joined: Apr 10, 2012
Posts: 33
Hey, There are two overloaded functions of Collections class for sortting of which Collections.sort(List<T> list) takes list of objects ie. list that implements comparable interface and Collections.sort(List<T> list ,comparator<T> rule) takes a list and a sorting rule defines by implementing Comparator interface. When you call Collections.sort(list) and list object is a comparable then when sort method performs, it internally invokes compareTo() method defined in comparable implementer class.

Accordingly your code



When you call Collections.sort(dvdList), it internally call the above compareTo method. As there inside compareTo function, title.compareTo(d.getTitle()) is written, sorting is actually performs by title. And If you would write genre.compareTo(d.getGenre()) , then sorting would be done by using genre. Sorting rules are defined in compareTo method for the case of implementing comparable interface and in compare method for the case of implementing comparator interface for defining sorting rules or sorting logic.


gurpeet singh
Ranch Hand

Joined: Apr 04, 2012
Posts: 923
    
    1

thanks alot Helen and Rahman. I would like to know internally which sort algorithm does Collections.sort() method uses ?
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

gurpeet singh wrote:I would like to know internally which sort algorithm does Collections.sort() method uses ?


Look at the documentation for java.util.Collections#sort(java.util.List) then - that tells you.
gurpeet singh
Ranch Hand

Joined: Apr 04, 2012
Posts: 923
    
    1

thanks all. the problem as well as confusion is solved. diving into more details as to how the algorithm is implemented (TIMSORT ALGORITHM) would be an overkill for me. That would be more or less for phd guys.
thanks once again.
gurpeet singh
Ranch Hand

Joined: Apr 04, 2012
Posts: 923
    
    1

thanks everyone. Yes helen i would like to know how to sort in descending order. I have understood the ascending scenario.
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
gurpeet singh wrote:thanks everyone. Yes helen i would like to know how to sort in descending order. I have understood the ascending scenario.

All you have to do is reverse the order in the compareTo method:

Ascending:


Descending

Note that this assumes that neither d nor d.getTitle will be null; if it's possible they could be null you would want to add checks before the comparison of titles.
gurpeet singh
Ranch Hand

Joined: Apr 04, 2012
Posts: 923
    
    1

thanks Dennis. I would like to know one thing when we say Obj1.compareTo(Obj2) does it mean that Obj2 is the next element in the collection/array ? Also if the answer is yes does, same thing hold in comparator implementation compare(Obj1, Obj2). also does objects get swaped only when we get a positive return value from above these two methods as said by Helen in her post ???
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

Dennis Deems wrote:
All you have to do is reverse the order in the compareTo method:

There are actually a couple of methods in java.util.Collections that will do that for you. One will return a Comparator that reverses the natural order, and the other can take any Comparator and will return another that works in reverse.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

gurpeet singh wrote:when we say Obj1.compareTo(Obj2) does it mean that Obj2 is the next element in the collection/array ?

Not necessarily. That entirely depends on the implementation of the sort() method, which is entirely separate from the compareTo() method. The only thing that method ever knows, or has to know, is that it's comparing two objects.
gurpeet singh
Ranch Hand

Joined: Apr 04, 2012
Posts: 923
    
    1

okay i got the point that compareTo() method or compare() method just compare two objects and that sort method has its own implementation which i guess is a modified version of mergesort and that sort method uses information/sort criteria from the above methods. so when i did this:

code listing 1.



In code listing the result will be sorted in an ascending order. and for descending order we have to do like this:

Code listing 2.



so we just memorize this thing that for descending order sorting we just reverse the positions of the object because as Dennis said that compareTo() and compare methods just compare two objects , which one is first or second in the list is of no concern.

Secondly is it right that if the integer returned by compare method is positive the objects gets swaped as said by helen in her post. Please verify. I'm having trouble in absorbing this concept.
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Matthew Brown wrote:
Dennis Deems wrote:
All you have to do is reverse the order in the compareTo method:

There are actually a couple of methods in java.util.Collections that will do that for you. One will return a Comparator that reverses the natural order, and the other can take any Comparator and will return another that works in reverse.

This is true, but I think the poster's question is more about how it works than about what API he can call.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

Dennis Deems wrote:This is true, but I think the poster's question is more about how it works than about what API he can call.

Maybe. But if you want to reverse an existing ordering, this is the best practice to use. It's less error prone, and better shows the intent of the code.

Imagine I've got a natural ordering that involves a number of different fields, and is quite complicated. Which is clearer - a fully implemented Comparator that reverses that logic, or Collections.reverseOrder()?
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Matthew Brown wrote:
Dennis Deems wrote:This is true, but I think the poster's question is more about how it works than about what API he can call.

Maybe. But if you want to reverse an existing ordering, this is the best practice to use. It's less error prone, and better shows the intent of the code.

Imagine I've got a natural ordering that involves a number of different fields, and is quite complicated. Which is clearer - a fully implemented Comparator that reverses that logic, or Collections.reverseOrder()?

I agree with you, but clarity of code is a concern that is not relevant to the exam.

Gurpeet, I recommend that you write about a dozen small, simple programs -- some that use compareTo and others that use Comparator -- and the only thing these programs should do is sort a little collection of Integer or String objects. Also, write at least one program that avoids using the API and perform the comparison logic yourself.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Need help in understanding how Comparable and Comparator works ?
 
Similar Threads
Collections and array Problem
how is toString method used in this question
Confused about use of compareTo()
Collections.sort() on Array List
Comparable interface problem