javatimsort

TimSort violation


What's wrong with this comparator method?

I have read : Java error: Comparison method violates its general contract

And understand that if c1 > c2, and c2 > c3, then c1 > c3. I believe this should hold true in the above.

getMaxCosine() returns value between 0..1, and 2nd sort is by the length of the text in the card, the longer the higher ranked.

public int compare(Card c1, Card c2) {
   if (getMaxCosine(c1) > getMaxCosine(c2)) {
       return -1;
   } else if (getMaxCosine(c1) == getMaxCosine(c2)) {
       return getMatchingText(c1).length() >= getMatchingText(c2).length() ? -1 : 1;
   } else {
       return 1;
   }
}

Solution

  • I think your issue is in your if-else block:

    else if (getMaxCosine(c1) == getMaxCosine(c2)) {
           return getMatchingText(c1).length() >= getMatchingText(c2).length() ? -1  : 1;
    }
    

    If getMatchingText(c1).length() is equal to getMatchingText(c2).length() then you return -1. This yields an "unstable" sort: In other words, the order two objects with equal values will be reversed after sorting. Moreover, you should return 0 for Cards that are equal under this comparator. I suggest changing the >= comparison to just > in this if-else block:

    else if (getMaxCosine(c1) == getMaxCosine(c2)) {
           if (getMatchingText(c1).length() == getMatchingText(c2).length()) return 0;
           return getMatchingText(c1).length() > getMatchingText(c2).length() ? -1  : 1;
    }