How to sort an array of segments (int left, int right) in a ascending order but if left(i)=left(i+1) sort it acording to right(i) and right(i+1)

Question

I have a class Segment and an array of segments like this:

private static class Segment {
        int number, type;
        Segment(int number, int type) {
            this.number = number;
            this.type = type;
        }
}

Segment[] points = new Segment[n];
points={(0,-1),(1,0),(5,1),(6,0),(6,-1),(10,1),(11,0)}

The element of the left is a list of points, and the list of the right is the type of point: -1 opens a segment, 1 closes a segment and 0 intersects the segment. As you can see, this array is already sorted according to number, using this code (its an adapted selectionSort):

maxI finds the index of the biggest "number" element

private static int maxI(Segment[] segments, int size){
    int max=0;
    for (int i=0; i< size;i++){
        if(segments[i].number > segments[max].number ){
             max=i;
        }   
    }
    return max;
}

// swap method swaps elements of the array between index1 and index2

private static void swap(Segment[] segments, int index1, int index2){
            int temp1; 
            int temp2;
            temp1 = segments[index1].number;
            temp2 = segments[index1].type;
            segments[index1].number=segments[index2].number;
            segments[index1].type=segments[index2].type;
            segments[index2].number=temp1;
            segments[index2].type=temp2;
    }

selectSort is the sorting method (since Arrays.sort wont work with "segments")

private static void selectSort(Segment[] segments) {
        int MaxPos;
        for (int i=segments.length-1;i>0;i--){
            MaxPos = maxI(segments, i+1);
            swap (segments, MaxPos, i);
        }
}

The original input was 2 ranges and 3 intersection points:

Range 1: 0 5
Range 2: 6 10
Intersection points: 1 6 11

So after sorting, the result as above is:

(0,-1),(1,0),(5,1),(6,0),(6,-1),(10,1),(11,0)

I've tried to modify the maxI method, so 6,-1 comes before 6,0 (-1 < 0) using a second if statement:

if (segments[i].number = segments[max].number && segments[i].type > segments[max].type)

But it messes the output.Since the input is random, the code must be prepared to sort testcases where many numbers are equal.

The closest question I've seen with this subject is one made in C++, I'm just learning Java so I'm struggling enough to try to understand C++. I feel the answer is close, but not sure what am I missing.Maybe I'm using the wrong data structure. After this I just traverse the array, adding the sum of the types, so if a number passes 3 opening of ranges (x,-1), it's -3,in absolute= 3 so it's intersecting 3 ranges, which is the answer I'll need.

Answer 1

Just create a Comparator that compares number then type, then you can use Arrays.sort(). If you have Java 8, you can do it like this:

Arrays.sort(points, Comparator.comparingInt((Segment s) -> s.number).thenComparingInt((Segment s) -> s.type));

If you're using Java 7, you can do this:

Arrays.sort(points, new Comparator<Segment>() {
    @Override
    public int compare(Segment s1, Segment s2) {
        int result = Integer.compare(s1.number, s2.number);
        if (result == 0) {
            result = Integer.compare(s1.type, s2.type);
        }
        return result;
    }
});

Alternatively, you can have Segment implement the Comparable interface, and Arrays.sort(points) will work out of the box:

private static class Segment implements Comparable<Segment> {
    int number, type;
    Segment(int number, int type) {
        this.number = number;
        this.type = type;
    }

    @Override
    public int compareTo(Segment s) {
        int result = Integer.compare(this.number, s.number);
        if (result == 0) {
            result = Integer.compare(this.type, s.type);
        }
        return result;
    }
}