• 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

Need help in understanding how Comparable and Comparator works ?

 
Ranch Hand
Posts: 924
1
Netbeans IDE Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ?
 
Ranch Hand
Posts: 451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.


 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 924
1
Netbeans IDE Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks alot Helen and Rahman. I would like to know internally which sort algorithm does Collections.sort() method uses ?
 
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 924
1
Netbeans IDE Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 924
1
Netbeans IDE Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks everyone. Yes helen i would like to know how to sort in descending order. I have understood the ascending scenario.
 
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 924
1
Netbeans IDE Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 924
1
Netbeans IDE Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 808
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 808
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic