Sort character array using java comparator

Question

Sort a character array lexicographically with an additional condition that all c's comes before all b's. This could be done manually but I want to code it via inbuilt sorting using comparators. The code I wrote -

static class Sort implements Comparator<Character> {
    @Override
    public int compare(Character x, Character y) {
        if(x == 'c' && y == 'b') {
            return y - x;
        }
        return x - y;
    }
}

public static void main(String[] args) {
    String s = "abracadabra";
    int n = s.length();
    Character[] res = new Character[n];
    for (int i = 0; i < n; i++) {
        res[i] = s.charAt(i);
    }
    Arrays.sort(res, new Sort());
    System.out.println(Arrays.toString(res));
}

Gives output: [a, a, a, a, a, b, c, b, d, r, r]. The c only comes before one of the b's. If I change the comparator to the following then it gives the correct output.

public int compare(Character x, Character y) {
        if(x == 'c' && y == 'b' || x == 'b' && y == 'c') {
            return y - x;
        }
        return x - y;
    }

My question is why in both cases returning "y-x" gives the correct answer? If in one case returning "y-x" was correct then in the other case shouldn't returning "x-y" would have been correct? Instead of "y-x", returning a -1 or +1 doesn't work either. Pl. explain what is happening internally. Thanks!

Answer 1

The problem is that if passing 'c' and 'b' makes the comparison return a negative value, then passing 'b' and 'c' should return a positive one (And your first version returns a negative number in that case instead). If the function doesn't return consistent results no matter the order of arguments, the sort algorithm is going to produce a garbage order.

Consider this version:

    public int compare(Character x, Character y) {
        if (x == 'c' && y == 'b') {
            return -1;
        } else if (x == 'b' && y == 'c') {
            return 1;
        } else {
            return x.compareTo(y);
        }
    }