*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes need help in understanding Comparator ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "need help in understanding Comparator ?" Watch "need help in understanding Comparator ?" New topic
Author

need help in understanding Comparator ?

gurpeet singh
Ranch Hand

Joined: Apr 04, 2012
Posts: 924
    
    1

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.
Md. Minhajur Rahman
Ranch Hand

Joined: Apr 10, 2012
Posts: 33
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.

dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
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.)
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4338
    
    7

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.
Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2271
    
  28

Gurpeet,

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
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.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3573
    
  14

Perhaps, but people should not rush to find out how the engine works before they figure out how to open the bonnet.
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Stephan van Hulst wrote:Perhaps, but people should not rush to find out how the engine works before they figure out how to open the bonnet.

Very true!
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4338
    
    7

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.
Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2271
    
  28

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.
Helen Ma
Ranch Hand

Joined: Nov 01, 2011
Posts: 451
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.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3573
    
  14

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.

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: need help in understanding Comparator ?
 
Similar Threads
priority queue!
Generics
Priority queue
Regarding PriorityQueue
Doubt in Using the PriorityQueue Class