0:01
Next we'll take a look at comparators which is a Java mechanism that helps us
sort. The same data on different sort keys, different orders. And you're
familiar with this. Your music library maybe I, at one point, you sort it by the
artist's name. In this case we're looking at the b's. But in another situation, you
might want to sort it by song names to look through it by song names. That's the
same data using different sort keys. How do we arrange to do something is natural
as this in our Java sorts? Now, we use the fourth in order to be able to implement
sorts that can sort any type of data, we use Java's Comparable interface. And that
concept is that there's some natural ordering of the data that you'll want to
use most of the time, that's what the Comparable interface is all about. But
there's a different interface called the Comparator Interface which is a way to
help a sort, using some alternate order or many different orders on the same data.
And the Comparator interface again just says that it's going to implement a method
compare() that compares two different keys of the given type, of the generic type.
Again it has to be a total order and this is very familiar for example with strings.
There's many different ways that we might want to sort strings. We might want to use
the natural alphabetic order or we might want to make it case insensitive or maybe
there is just different languages that have different rules of the ordering.
We're sorting strings but we're implementing a different ordering, various
different orderings on that same data. That's what the Comparator interface is
for. So the Java system sort will have a different. [cough] method to implement
comparators. The idea is that you create a comparator object and then pass that as a
second argument to Java's sort routine and we can do the same thing for our sorts.
The idea is when a decouple, the definition of the data type from the
definition of what it means to compare to items of that type. With the natural
order, we had to put the definition compared to within the data type. With
comparators, we can do that outside of the data type even at some later time. Strings
were defined and as part of the Java system but we can define our own ordering
on strings with the comparator. So in our sort implementations we can change them as
shown in this example to support comparators. To support comparators in our
sort implementations we'll pass an array of objects and instead of an array of
comparable and then, there's a second argument passed a comparator. Then, the
less method will take that comparator as an argument and this is the one that
actually invokes the method compare two different keys. This is a straightforward
modification to our sorts. And then exchange of course rather doing comparable
has to use object. So with these straightforward changes at the comparator
as argument to the sort and to less and make array to be sorted array of objects,
it's easy to convert any of our implementations to support comparators. To
implement a comparator you can use this code as a model. I won't go through it all
in detail just to point out that this implements two different comparators as
nested classes. Say, for this fictional class Student, that's got two instance
variables - name and section. And the first one called by name implements a comparator
for students and when you compare two students by name, it's going to use the
string comparative method. If you're going to implement it compared to students by
section, then it'll return just the difference of the sections which is my
minus if less zero if equal then plus if greater. And this code is straight forward
way to implement comparators that you can use as a model. If you need to be able to
sort data on two different keys. So [cough] here is just an example of what
happens if would those implemented comparators for that class student using
the Java system sort, if you call array that sort with your a rray of students and
you give it this by name comparator, it will put them in order alphabetical order
by the name field. And if you give it to by section comparator, it will them in
order by the second field very convenient for all kinds of data processing
applications. And we came up with that before when we're talking about using a
sort for the Graham scan. We needed to have a comparison for points that orders
them by the polar angle they make, make with the given point p. That's what we
needed for the Graham scan algorithm for the convex hull. Points are defined data
type for geometric objects and so what we need is code that will compute the polar
angle and use that as the basis for comparison. There's an easy way to do this
based on CCW that is described here in this text. Most of the time all you need
to do is do the CCW of the two points. You either have to check whether [cough] the,
one of the points is above p and the other one is below. But otherwise, usually it's
a CCW call in this code which again I won't go through in detail as an
implementation of a comparator for two D points. It implements the compare method
that takes two points as argument and with just a little bit of calculation is able
to do the compare. So this code is the basis for applying the sort, system sort
method or any sort method for the Graham scan for the convex hull that we did at
the end of the last lecture. So that's the basis for the Graham scan method for the
convex hull that we used at the last, at the end of the last lecture.
Kevin WayneSenior Lecturer
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
