Sorting arrays in 3 steps in Java

Question

I have two arrays representing points in a 3D space, position[] for XYZ and colors[] for RGB, both with size 3*total_points (e.g. position[0] is X, position[1] is Y, and position[2] is Z coordinate of point 0, and color[0] is the Red value, color[1] is Green, and color[2] is Blue).

What I need to do is basically sort all points in 3 steps:

1. Sort based on X (position[0])
2. Then sort based on Y (position[1])
3. Then sort based on Z (position[2])

What is the most efficient way of doing this in Java?

What I have in mind is simply doing a bubble-sort -like approach and swap, and do this three times.

for (int i=0; i<position.length; i++){
  for (int j=0; j<position.length; j++){
    if(position[i] > position[j]){
    swap (position[i], position[j]);
   }
  }
}

// and do this for position[i+1] (i.e. Y) and then position[i+2] (i.e. Z)

Answer 1

One key point of object-oriented programming is abstraction. To achieve it, you should create a class that represents a coloured 3D point, such as:

public class Point {

    private final int x;

    private final int y;

    private final int z;

    private int red;

    private int green;

    private int blue;

    public Point(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    @Override
    public String toString() {
        return "(" + x + ", " + y + ", " + z + ")";
    }

    // TODO getters for x, y and z, plus getters & setters for red, green and blue
}

Note: I've added a very useful toString() method that will help you debug your code. Getters and setters are left as an exercise :)

Now, if you have an array of points, i.e. Point[] points, you can use the built-in Arrays.sort utility method, which accepts an array and a Comparator<Point>:

Point[] points = new Point[] {
    new Point(2, 3, 1), 
    new Point(2, 1, 4), 
    new Point(2, 1, 5) };

System.out.println(Arrays.toString(points)); // [(2, 3, 1), (2, 1, 4), (2, 1, 5)]

Comparator<Point> comparator = Comparator.comparingInt(Point::getX)
    .thenComparingInt(Point::getY)
    .thenComparingInt(Point::getZ);

Arrays.sort(points, comparator);

System.out.println(Arrays.toString(points)); // [(2, 1, 4), (2, 1, 5), (2, 3, 1)]

Note: I'm using Arrays.toString utility method to create a human-readable string representation of the array.

Pay attention to the definition of the Comparator<Point> comparator variable: there I'm stating that I want a comparator that will order points based on the int value returned by the Point.getX() method, then, if equal, order will be determined by the int value returned by the Point.getY() method and, finally, if still equal, order will be determined by the int value returned by the Point.getZ() method. This is what the Comparator.comparingInt and Comparator.thenComparingInt methods are used for.

Answer 2

As is mentioned in the other answer, abstraction is a key point (i.e. from your three arrays of ints that loosely represent a set of points to an array of actual Points). This way, you always have the three expected coordinates together every time you handle them.

To further improve on the answer, you would probably gain from separating even more:

class Point {
    int x, y, z; // plus getters/setters
}

class Color {
    int r, g, b; // dito
}

class ColoredPoint {
     Point point;
     Color color;
}

Now you have the point and the color separate when you don't need them, but together when you do (as you needed in the original question IIUC). This is called "separation of concern" - a position in space and a color are different beasts, it's best to keep them apart.

With respect to sorting, you can also do all kinds of sorting by using different Comparators.

Comparator<Point> pointComparator = Comparator.comparingInt(Point::getX)
    .thenComparingInt(Point::getY)
    .thenComparingInt(Point::getZ);
// and 
Comparator<Color> colorComparator = Comparator.comparingInt(Color::getR)
    .thenComparingInt(Color::getG)
    .thenComparingInt(Color::getB);

Because you used composition to combine Point and Color together, you can reuse those comparators for your ColoredPoint if needed:

Comparator<ColoredPoint> cpComparator =
    Comparator.comparing(ColoredPoint::getPoint, pointComparator)
    .thenComparing(Comparator.comparing(ColoredPoint::getColor, colorComparator));

This is better than my previous answer, which looked like this:

class Point implements Comparable<Point> {
    int x, y, z;

    // you can also create a separate Comparator<Point> 
    // to move the compare code outside of Point
    int compareTo(Point other) {
        // compare by position in space
        int result = this.x - other.x;
        result = (result == 0) ? result : this.y - other.y;
        result = (result == 0) ? result : this.z - other.z;
        return result;
}

Point[] arrayOfPoints = //...
Arrays.sort(arrayOfPoints);
// or
List<Point> listOfPoints = //...
Collections.sort(listOfPoints);

Again due to separation of concern, the point does not really need to know how you want it sorted.