Solved

Sorting array of coordinates

Posted on 2008-10-19
2,044 Views
Hi, I have a collection of coordinates x, y (doubles) i.e. (3.4, 5.3), (3.0, 5.5), and so on...

I put them into an array and I need to sort them based on either coordinate. I need to use the sort method from the java.util.Arrays class.

I imported the class, created an array in which I put all my coordinate objects. I'm not sure how the Arrays.sort() method works. How do I go about sorting the array based on either coordinate (x or y).

Let's say that I have :

Coordinate [] myArray = {c1, c2, c3, c4, ...cn} where each c is a coordinate i.e c1 = (3.4, 5.5)

Once again I need to use the built in method in the Arrays class.

Would I have to do something like,
Arrays.sort(myArray.getX()) getX() gets the x cordinate
in order to sort all the coordinates in increasing order of the X coordinate?

Sorry if this seems a trivial question, but even when I create an array on int's (int [] myArray), and I do Arrays.sort(myArray), the code doesn't compile.

p.s. I need to use the Arrays.sort() method, no need to create my own implementation.
0
Question by:ubuntuguy
• 2
• 2

LVL 4

Accepted Solution

petr_hlucin earned 500 total points
ID: 22753506
What you should do is use the following version of Sort:
static void sort(Object[] a, Comparator c);

The Comparator and Coordinate would be the following in your case.
``````class CoordinageComparator implements Comparator{

public int compare(Coordinate coordinate1, Coordinate coordinate2) {
return coordinate1.compareTo(cordinate2);
}
}

class Coordinate {
public double X;
public double Y;

public CompareTo(Coordinate c) {
if (c.X < this.X)
return -1;
else if (c.X > this.X)
return 1;
else
return 0;
}
}
``````
0

LVL 1

Author Comment

ID: 22753744
Hmmm, I thought about doing it this way, but my method must run in O(nlogn) and this would run in O(n^2).  I know the Arrays.sort() runs in O(nlogn), but I'm unsure on how to implement it.
0

LVL 4

Expert Comment

ID: 22753807
IMHO this would run in O(n*log(n)) - CompareTo() runs in O(1) and Sort by itself runs in O(n*log(n)). If you think that sort with Comparator runs in O(n^2) you may write your own sort :-). No, seriously I'm almost sure that Sort with Comparator runs in O(n*log(n)) and therefore the following code together with the one posted with my previous post should solve your problem in O(n*log(n)).
``````Coordinate[] c = new Coordinate[50];

Arrays.Sort(c, new CoordinateComparator());
``````
0

LVL 1

Author Closing Comment

ID: 31507638
thanks, you were right.
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question