1
private static class CharacterIndex implements Comparable<CharacterIndex> {
    private final char c;
    private final int index;

    public CharacterIndex(char c, int index) {
        this.c = c;
        this.index = index;
    }
}

Now I want to override the compareTo method for this class such that if I have the following List of CharacterIndex's objects [('y', 1), ('x', 2), ('b', 3), ('a', 3)] then after sorting, the objects should be like [('b', 3), ('a', 3), ('x', 2), ('y', 1)].

Sorting Strategy:

Objects for which the index is different can be shuffled (and should be in sorted order based only on the character's value). Objects that have same index should maintain their relative order after sorting.

One more example:

For [('y', 1), ('w', 2), ('x', 3)] the sorted list should be [(w, 2), (x, 3), (y, 1)] and not [(x, 3), (w, 2), (y, 1)].

My attempt:

@Override
public int compareTo(CharacterIndex ci) {
    if (this.index == ci.index)
        return -1; // don't swap if the index is same
    return Character.compare(this.c, ci.c);
}

But this approach gives me an exception:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
    at java.util.Arrays.sort(Arrays.java:1312)
    at java.util.Arrays.sort(Arrays.java:1506)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at java.util.Collections.sort(Collections.java:141)

I saw this. But I couldn't clearly understand why am I getting this exception.

Is there a better way to sort the List<CharacterIndex> with the above given strategy?

Lavish Kothari
  • 2,211
  • 21
  • 29
  • `return -1; // don't swap if the index is same` That's not what -1 means here. Returning -1 means that `this` sorts before `ci`. If what you want is for them to _not_ swap, then that means they sort the same, and that means you want to return 0. – yshavit Mar 10 '19 at 16:58
  • @yshavit That's not exactly correct. If you return `0` it means the two elements are "equal" and may be shuffled among themselves, depending on the sorting algorithm. – RealSkeptic Mar 10 '19 at 17:22
  • @RealSkeptic True. I was trying to keep things relatively simple and shortcut that a bit, since the JDK sorting algorithms are all (afaik) stable. But that's a good call-out for the next level of detail. – yshavit Mar 10 '19 at 17:27
  • 2
    Your sorting strategy does not seem to define a proper total order. For example, consider `(b,1),(c,3),(a,3)`. How do you order them? The `(b,1)` has to come before the `(c,3)`, but after the `(a,3)`, but since you can't reorder the `(c,3)` and the `(a,3)`, you cannot order this combination at all. – RealSkeptic Mar 10 '19 at 17:34

2 Answers2

1

Putting @RealSkeptic's comments into answer:

The java-docs of Comparable says that:

This interface imposes a total ordering on the objects of each class that implements it.

Total-ordering should follow the following properties:

  • Reflexivity
  • Antisymmetry
  • Transitivity
  • Comparability

To see more on what totally ordered sets are see this link.

My sorting strategy is not transitive.

Suppose my initial list is [(d,2), (y,1), (b,1)]

  • (y,1) < (b,1) as for same index, I don't want to shuffle the order.
  • (b,1) < (d,2) as for different index, I can shuffle order and then I need to compare the character only.

By transitivity, (y,1) < (d, 2). Which is not true.

So this is not a totally ordered comparison. And hence it breaks the rule provided by Comparable interface.

So we can't have a correct implementation of compareTo (which abide by the contract of Comparable interface) for this sorting strategy.

What you learned?

Your sorting strategy should always define total ordering on the objects of class that implements Comparable

Lavish Kothari
  • 2,211
  • 21
  • 29
  • 1
    Another important thing you should have learned is that returning `-1` doesn't mean "do not switch". In classical quicksort, for example, you pick a "pivot", and put everything that's lower to its left, and everything that's higher to its right. This would mean that elements that returned `-1` *would* be moved before that element. – RealSkeptic Mar 11 '19 at 09:50
0

It's because you have o1.compareTo(o2) == -1 && o2.compareTo(o1) == -1 if o1.index == o2.index. The contract for compareTo method is that those two must be of different signs: o1.compareTo(o2) and o2.compareTo(o1).

In other words this means both that o1 is less than o2 and o2 is less than o1, which is impossible.

Possible solution:

@Override
public int compareTo(CharacterIndex ci) {
    return Character.compare(this.c, ci.c);
}

Here we are comparing by character it carries. As @RealSkeptic noticed, there is no way to take index into account as the relation is no longer transitive.

Andronicus
  • 25,419
  • 17
  • 47
  • 88