Need help in understanding how Comparable and Comparator works ?

[gurpeet singh]

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

class DVDInfo implements Comparable<DVDInfo> {
String title;
String genre;
String leadActor;
DVDInfo(String t, String g, String a) {
title = t; genre = g; leadActor = a;
}
public String toString() {
return title + " " + genre + " " + leadActor + "\n";
}
public int compareTo(DVDInfo d) {
return title.compareTo(d.getTitle());
}
public String getTitle() {
return title;
}
// other getters and setters
}

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 ?

[Helen Ma]

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]

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

.
.
.

public int compareTo(DVDInfo d) {  
return title.compareTo(d.getTitle());  
}  
.
.
public String getGenre() {  
return genre;  
}  
.
.

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]

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

[Matthew Brown]

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]

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]

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

[dennis deems]

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:

 public int compareTo(DVDInfo d)
{  
    return title.compareTo(d.getTitle());  
}  

Descending

public int compareTo(DVDInfo d)
{  
    return d.getTitle().compareTo(title);  
}  

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]

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]

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]

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]

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.

 public int compareTo(DVDInfo d)  
{    
    return title.compareTo(d.getTitle());    
}    

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.

 public int compareTo(DVDInfo d)  
{    
    return d.getTitle().compareTo(this.title);    
}  

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]

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]

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]

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.