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!

If you invert the arguments, you have to negate the result.

Maurice Perry
– Maurice Perry

2021-12-17 10:57:07 +00:00
Commented Dec 17, 2021 at 10:57 — Maurice Perry
– Maurice Perry, Commented Dec 17, 2021 at 10:57

Shawn · Accepted Answer · 2021-12-17 11:06:32Z

4

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);
        }
    }

edited Dec 17, 2021 at 11:06

answered Dec 17, 2021 at 11:01

Shawn

53.9k3 gold badges29 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Shawn Over a year ago

(I'm not a big fan of using subtraction to compare two values; been bitten by overflow issues a few times in C programs that did that)

Agzam · Accepted Answer · 2021-12-17 11:12:20Z

You can add System.out.println() to understand how it work:

Code

import java.util.Arrays;
import java.util.Comparator;

public class Main {

    public static void main(String[] args) {
        String s = "abracadabra";
        int n = s.length();
        
        System.out.println("X Y\tX Y\t[if] VALUE");
        System.out.println();
        
        Character[] res = new Character[n];
        for (int i = 0; i < n; i++) {
            res[i] = s.charAt(i);
        }
        
        int min = 'a';
        
        Arrays.sort(res, new Comparator<Character>() {

            @Override
            public int compare(Character x, Character y) {
                System.out.print(y + " " + x + "\t" + (x-min) + " " + (y-min) + "\t");
                if(x == 'c' && y == 'b') {
                    System.out.println("true " + (y - x));
                    return y - x;
                }
                System.out.println("     " + (x - y));
                return x - y;
            }
        });
        System.out.println("#################################\nResult:\n" + Arrays.toString(res));
    }
}

Console:

X Y X Y   [if] VALUE

a b 1 0        1
b r 17 1       16
r a 0 17       -17
b a 0 1        -1
a a 0 0        0
b c 2 1   true -1
a c 2 0        2
c a 0 2        -2
a a 0 0        0
c d 3 2        1
r d 3 17       -14
b d 3 1        2
c a 0 2        -2
a a 0 0        0
a a 0 0        0
c b 1 2        -1
a b 1 0        1
a b 1 0        1
b r 17 1       16
d r 17 3       14
r r 17 17      0
c a 0 2        -2
a a 0 0        0
b a 0 1        -1
a a 0 0        0
#################################
Result:
[a, a, a, a, a, b, c, b, d, r, r]

tquadrat · Accepted Answer · 2021-12-17 11:24:36Z

0

See the Javadoc for java.util.Comparator. It says for the method compare():

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

For your case, it means that compare( 'b', 'c' ) should return something greater than zero, and for compare( 'c', 'b' ) something less than zero, while the natural order would be the opposite.

But your first implementation (that wrong one) covered only the case compare( 'c', 'b' ), but not compare( 'b', 'c' ), so that the method would return the default value then.

Your second and correctly working implementation fixed that.

answered Dec 17, 2021 at 11:24

tquadrat

4,1401 gold badge21 silver badges36 bronze badges

Collectives™ on Stack Overflow

Sort character array using java comparator

3 Answers 3

1 Comment

Code

Console:

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Code

Console:

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related