Java Sort by Distance

I have a 2-dimensional array like this:

{1,3,5,6,2,2}

{6,2,4,7,2,1}

{17,28,32,1,35,45}

...

I have a function that can calculate the euclidean distance between any two arrays. Assuming that the distance function operates correctly, what's the best way to sort the 2-dimensional array so that the arrays within the 2-dimensional array are swapped such th开发者_StackOverflowat the one's closest to each other(distance wise) would be close to each other in the 2-dimensional array?

Edit

Is this boiling down to the travelling salesman problem again?

I'd use a TreeSet and a comparator.

public class EuclidComparator implements Comparator<int[]> {

    @Override
    public int compare(int[] o1, int[] o2) {

        return euclid_distance(o1, o2);

    }

}

Sort with:

    TreeSet<int[]> sort = new TreeSet<int[]>(new EuclidComparator());
    sort.addAll(Arrays.asList(arrays));

Or even easier:

    Arrays.sort(arrays, new EuclidComparator());

I would start by calculating all distances between the arrays and storing them in a TreeMap then create a map that is the reverse of this map and proceed with the sorted values to sort the arrays.

You must see that there is no "perfect" solution, where perfect would mean that "If entries A and B are adjacent in my array, then no point is closer to A than B is, and no point is closer to B than A is".

This is simply not possible.

As I think about the problem, I believe that you need to calculate the distance from every point to every other point to know which is closest to which. So you have to effectively have a NxN grid for N points, no?

Then once you have the distance from Nsubn to ever other Nsubn, you need a ranking method to reduce the resulting matrix a-la linear algebra, no?

I presume it reduces to a matrix like this:

A {1,1,1}

B {3,3,3}

C {5,5,5}

And since the distance between each of those is desired to be the square root of 12, then you would have a matrix like thus:

         A         B         C
A        0  sqrt(12)  sqrt(48)
B sqrt(12)         0  sqrt(12)
C sqrt(48)  sqrt(12)         0

Since this is upper and lower diagonal, you can eliminate half of the grid and solve the other half... At this point it should be a solvable problem, no?

For reference, here's a different sample:

see also: http://www.wolframalpha.com/input/?i=distance+between+(5,1,3)+and+(3,5,1)

A {1,3,5}

B {5,1,3}

C {3,5,1}

Then you would have a matrix like thus:

         A         B         C
A        0  sqrt(24)  sqrt(24)
B sqrt(24)         0  sqrt(24)
C sqrt(24)  sqrt(24)         0

and this tells us all the points are equidistant from one another.

Or did I go way off into left field on this one? What did I miss?

Perhaps the "post-sort" data structure you're looking for is a map of each point to its two nearest neighbors, not a two-dimensional array? Unless I'm missing some property of your problem domain which makes this possible, you can't apply a linear order to the points in your problem space.

Write a quicksort, and use your distance function when you have to compare two elements. Wikipedia's got the algorithm for you.