Large data set sorting problems

Question

I have a 2-D array respresenting the x and y coordinates of a grid of points making up a rectangle. The data sets being used are typically very large. I want to sort the points starting in the top left hand corner and moving in parallel diagonal lines until the bottom right hand corner. I'm using the Arrays.sort function and the following comparator to do it:

public int compare(Object o1, Object o2) {
  double[] a1 = (double[])o1;
  double[] a2 = (double[])o2;

  if (a1[0]+a1[1] > a2[0]+a2[1]) return 1;
  else if (a1[0]+a1[1] < a2[0]+a2[1]) return -1;
  else {
    if (a1[0] > a2[0]) return 1;    
    else if (a1[0] < a2[0]) return -1;
    else return 0;
  }  
}

The code works for some reason when the x and y coordinates of each point are spaced two digits apart, but there are errors in the sort if they're spaced only one digit apart.

An example of the original order can be found here: http://www.mediafire.com/?slq73v3zn2zs98l

And an example of what the resulting sorted list is looking like can be found here: http://www.mediafire.com/?x8f08q0qoof398w

Why isn't the sort working? Any help would be so very much appreciated!

Answer 1

Looking at the picture you have linked to, I think you want to do Double.compare() on the L1 distance of the point from the top left corner.

This means, given 2d points a and b, and "origin" Origin (in this case the top-left point) you want to compare:

distance_a = Math.abs(Origin.x - a.x) + Math.abs(Origin.y - a.y)
distance_b = Math.abs(Origin.x - b.x) + Math.abs(Origin.y - b.y)
return Double.compare(distance_a,distance_b);

and sort by comparing these distances. You could wrap this up into a sensible comparator that uses Double.compare().

Update: I understand the extra sorting criteria now, after your last comment. You may want to consider precision issues when comparing doubles (someone else will be able to advise you better), however you want something roughly like:

distance_a = Math.abs(Origin.x - a.x) + Math.abs(Origin.y - a.y)
distance_b = Math.abs(Origin.x - b.x) + Math.abs(Origin.y - b.y)
if distance_a is not equal to distance_b // check how you should perform the comparison
    return Double.compare(distance_a,distance_b);
else
    return Double.compare(a.x,b.x);