How to sort an array or ArrayList<Point> ASC first by x and then by y?

Question

Hi everyone,

I just want to use Collections.sort or Arrays.sort to sort a list of points (class Point) by x first and then by y.

I have a class Ponto that implements Comparable like this:

public int compareTo(Ponto obj) {
        Ponto tmp = obj;
        if (this.x < tmp.x) {
            return -1;
        } else if (this.x > tmp.x) {
            return 1;
        }
        return 0;
    }

but now I want to sort by y too after x.

How can I do that by modifying the above code? Or is that a better and "clean" way to do this? I also use to pass this code to C++, in which I've created a structure called Point with a equivalent comparable method.

Answer 1

Replace return 0 by the same comparison algo on this.y and obj.y.

By the way, reassigning to tmp is unnecessary here. The optimized picture can look like:

public int compareTo(Ponto other) {
    if (this.x == other.x) {
        return (this.y < other.y) ? -1 : ((this.y == other.y) ? 0 : 1);
    } else {
        return (this.x < other.x) ? -1 : 1;
    }
}

Answer 2

BalusC provides the correct answer: basically you give priority to x over y. Here's a variant written using nested ternary operators that makes the priority clear.

public int compareTo(Ponto other) {
    return
      (this.x < other.x) ? -1 :
      (this.x > other.x) ? +1 :
      (this.y < other.y) ? -1 :
      (this.y > other.y) ? +1 :
      0;
}

Another way to do this, if you don't want to write a custom Comparator<T> for every priority scheme, is to do multiple sort using a stable algorithm.

If you want to order by x (primary), and then y (secondary), then:

• Sort on y first (!!!)
• Then sort on x using a stable sort

This is asymptotically still O(N log N) but of course you're doing multiple phases. It's convenient when you have many sorting criterias. Rather than writing the complex code, just do the multiple phase (and only optimize if/when proven necessary).

So if you have sorting keys k1, k2, k3, ..., kM, in that order of priority, you do:

• Sort on kM
• Stable sort on kM-1
• ...
• Stable sort on k1
• DONE!

Note that Collections.sort is stable.

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.