This week's giveaway is in the Android forum. We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line! See this thread for details.

Please consider the following code listing from kb6 book page no. 591

I just want to undestand how comparator works. i know that comparator compares two objects , here in our case two Integer objects and can return positive,negative or 0 value. further if we have compare(Object 1, Object2)
if the value returned is -ve , this means that object 1 is less than object 2, for +ve object 1 is greater than object 2 and for 0 they are both equal. what i want to know is that here how the comparator is used i.e. how the reverse order is achieved. what actually happens when we get negative value or positive value. i have posted this question earlier also in different context but i didnt got any answer. is it like that if we get positive value , the two objects are interchanged ? Please refer my earlier post http://www.coderanch.com/t/573512/java-programmer-SCJP/certification/help-understanding-Comparable-Comparator-works. please help me since comparator is used everywhere and i'm not able to move further.

Hello gurpeet, The compare() of comparator and compareTo() of comparable is used for same perspective use. Defining compare() method in comparator, compareTo() is used internally. Sometimes rather using compareTo() method, it's logic is defined such as it behaves as like compareTo() method by supply same return value as compareTo() do. That's exactly done the given program. In compare() method, it is written " return two - one" which is same as return two.compareTo(one), thus produce reverse order ie. descending order.

Please UseRealWords. When you write things like "-ve" and "+ve", it makes it difficult for me to understand your question.

Your intuition is correct about when entities are swapped. Sorting utilities and sorted data structures will call comparator.compare, and adjust the position of the elements accordingly. If you were to look at the Java source of these classes, you would see code that does this:

The sort routine is going to iterate over the entire collection and repeatedly compare pairs of elements until the collection is sorted. (In the Arrays class the sort is a merge sort that minimizes the number of comparisons that are required.)

While you could look into the source code for PriorityQueue to see how it uses Comparable and Comparator, and you could look at the source code for the sort routines you mention in your previous post, the important point is this:

You don't need to know.

The specifications state that all that is needed is that you supply a Comparable or Comparator that allows two objects to be compared. That's all you need to understand. There are lots of different ways of doing the sorting, but all of them can be reduced at the lowest level of their algorithm to "which of these two items is bigger".

Exactly how it is used is an implementation detail. Read the source code if you're interested. But it absolutely isn't necessary for you to "move further" unless you're writing sort algorithms.

Are you asking how does the Queue use the COmparator to sort the items? You need to understand how sorting works first. Any sorting algorithm needs a comparison algo to figure out the sort order. The Comparator is that comparison alogorithm

For example, I believe Priority Queue uses inserttion sort algorithm. So, in the offer method it does something like this

dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808

posted

0

I've noticed many contributors to Java Ranch have this characteristic in common: the failure to realize that all brains are not the same. For one brain, it's enough to know that all they have to do is turn the key in the ignition, and press the gas and brake pedals as required. For another brain this knowledge is meaningless unless they open the hood and see how the engine works. Objectively, yes, the car functions the same regardless. But the second brain will be troubled until the mystery of what goes on under the hood is revealed.

Dennis Deems wrote:I've noticed many contributors to Java Ranch have this characteristic in common: the failure to realize that all brains are not the same.

Assuming that was aimed at me: that's true. But it's very common to see questions where it's clear the questioner is getting confused over the difference between the specification and the implementation. You need to be able to make a clear distinction between the two, and in those cases I think it is helpful to address that confusion. When somebody has enough of an understanding of the principles that going into the detail is useful, it's usually obvious, but until you've reached that point I think you're better off concentrating on the things that matter.

In this specific case, wanting to know about how sort algorithms work is fine, and checking the source code is the only reliable way of going about it. But thinking that knowledge of the algorithms is required to understand Comparable and Comparator shows an important lack of understanding that I think is useful to counter. It's enough to realise that the ability to compare two objects is the only knowledge you need to be able to sort any collection.

I think you do need to know how sorting works to know how the Comparator is used. You don;t need to understand the actual implementation of the sort algorithm, but you do need to understand how sort algorithms work.

When a class implements a Comparator interface, it should override a compare method.
Inside the method, it defines how do you want to compare two elements.
For example,

one is the first element and two is the next element from the input. If two is bigger than one, it returns a positive number. The sorting algorithm will do this:
if compare method returns a positive, the algorithm will swap the two numbers. So, they are sorted in descending order.
if compare method returns a negative, the algorithm will not swap it to maintain the descending order.

How about this:

one is the first element and two is the next element from the input. If one is bigger than two, it returns a positive number. The sorting algorithm will do this:
if compare method returns a positive, the algorithm will swap the two numbers. So, they are sorted in ascending order.
if compare method returns a negative, the algorithm will not swap it to maintain the ascending order.

The priority queue has already difined the sorting algorithm.
You can define your own sorting algorithm in other class of course.

Helen, it should be noted that your implementation does not adhere to the Comparator contract. More specifically, it does not define a transitive relation.

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.