Java Comparator Arrays.sort()

Question

I want to sort an array of 2 dimensional arrays in Java according to some rules, let's say the distance from the origin. I saw several ways of doing it using Arrays.sort():

1) Arrays.sort(points, Comparator.comparing(p -> p[0]*p[0] + p[1]*p[1]));

2) Arrays.sort(points, (p1, p2) -> p1[0]*p1[0] + p1[1]*p1[1] - p2[0]*p2[0] - p2[1]*p2[1]);

3) Defining the class:

class Point implements Comparable<Point>{
     // class variables, constructor
     public int compareTo(Point p) {
         return (x*x + y*y).compareTo(p.x*p.x + p.y*p.y);
     }
}

An array pts of type Points is then created and Arrays.sort(pts) is used. My question is regarding 1) and 2): I see the difference between the but I do not understand when to use one and when to use the other and what exactly Comparator.comparing() is doing. Why is the first solution carrying the information just with one point while the second need two points?

Eran · Accepted Answer · 2019-09-26 10:34:35Z

Comparator.comparing is implemented as follows:

public static <T, U extends Comparable<? super U>> Comparator<T> comparing(
        Function<? super T, ? extends U> keyExtractor)
{
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
        (c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2));
}

i.e. it uses the Function you pass to it in order to transform each of the compared elements into a Comparable, and then uses the Comparable's compareTo method.

When you are passing the function p -> p[0]*p[0] + p[1]*p[1], you are converting each point to its sum of squares. Then, when the Comparator needs to compare two points, it compares the sum of squares of the two points, which is almost equivalent to computing the difference of the sums of squares of the two points (it's not exactly equivalent, since comparing two numbers by computing their difference can produce wrong output in case of numeric overflow).

That's exactly what your second Comparator - (p1, p2) -> p1[0]*p1[0] + p1[1]*p1[1] - p2[0]*p2[0] - p2[1]*p2[1] - does,

since p1[0]*p1[0] + p1[1]*p1[1] - p2[0]*p2[0] - p2[1]*p2[1] == (p1[0]*p1[0] + p1[1]*p1[1]) - (p2[0]*p2[0] + p2[1]*p2[1]).

Using Comparator.comparing() is safer, since it compares the sums of squares of the two points without computing their difference. It uses Double's compareTo() instead (assuming the coordinates of your points are Double or double).

In other words, the first alternative uses a Function that needs just one point since this function tells Comprator.comparing how to transform each of the 2 points.

On the other hand, the second alternative accepts 2 points (which are the required arguments of the Comparator.compare() method) and determines the relative order of these 2 points.

Joop Eggen · Accepted Answer · 2019-09-26 10:33:47Z

In 2) one has to make a comparison between both operands of the comparison with respect to some function. In 1) one just specifies the one function that delivers the value to be compared. Besides comparing there also is for numerical values (like here) comparingInt, comparingLong, comparingDouble.

So 1) is the simplest to read.

For points with doubles the hypotenuse can be used, the actual distance to the origin

Arrays.sort(points, Comparator.comparingDouble(p -> Math.hypot(p[0], p[1]));

And then the bad news:

Two dimensional distance sorting does not give a sequential order. Hence sorting will not work between two elements. You can only sort with respect to one fixed point. Say rank the array points with respect to some fixed point. Here you take the distance to the origin (0, 0).

Kayaman · Accepted Answer · 2019-09-26 10:36:36Z

Using Comparator.comparing() you're saying "I want to use this property when comparing objects of this class". The property needs to be Comparable, so you see it used often with numeric properties, for example: Comparator.comparing(MyObject::getId) returns a Comparator with the logic "compare MyObjects by using their numeric id".

With (p1, p2) -> you're doing more work yourself. You're given 2 objects, and you need to return -1, 0 or +1 depending on whether p1 is is lesser, equal or greater to p2. This allows for more complex logic, but is more verbose and less readable than the first option if you're sorting based on one or a few properties.

Lastly you're making the class itself implement Comparable. This is usually referred to as the natural ordering. A Point doesn't really have a natural ordering like for example numbers, so creating a compareTo method is not something I'd advise.

Collectives™ on Stack Overflow

Java Comparator Arrays.sort()

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related