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!
CodePudding user response:
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);
}
}
CodePudding user response:
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]
CodePudding user response:
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.