CODEWITHSUNDEEP
java
Martin Snyder
Martin Snyder

Reputation: 528

How does this Java Comparator function properly?

I recently came across a comparator that on the surface looks incorrect. However, I've been unable to come up with an input to it that causes the comparator to produce the wrong result.

It incorrectly treats values as equal if o1 <= o2, and correctly returns 1 if o1 > o2.

I've tried to simplify the scenario as much as possible below. Can anyone either:

  1. Explain why this is ok.
  2. Produce an input array that causes it to sort the output incorrectly.

I've experimented with it quite a a bit and I'm throwing in the towel!

package comparator;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class BadComparator implements Comparator<Integer>
{
    public int compare(Integer o1, Integer o2)
    {
        // Generally Accepted implementation
        //return o1 - o2; 

        // Incorrect(?) Implementation
        return (o2 < o1) ? 1 : 0;
    }

    public static void main(String[] args)
    {
        List<Integer> intList = Arrays.asList(10, 9, 8, 1, 2, 3, 7, 4, 5, 6);
        Collections.sort(intList, new BadComparator());
        System.out.println(intList);
    }
}

Upvotes: 4

Views: 1712

Answers (4)

Dustin Getz
Dustin Getz

Reputation: 21801

Collections.sort is implemented as mergesort. looking at the source, all compare conditions are >0 or <=0 which by chance treat the negative case the same as the equal case. a different sort implementation can fail.

Per jbellis's comment, "It's not quite "just luck," though -- Collections.sort is guaranteed to be "stable," meaning that equal elements must be in the same relative order post-sort. I'm not sure it's impossible to come up with a stable sort implementation that fails with this comparator, but I can't think of one off the top of my head."

private static void mergeSort(Object[] src,
              Object[] dest,
              int low, int high, int off,
              Comparator c) {
int length = high - low;

// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
    for (int i=low; i<high; i++)
    for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
        swap(dest, j, j-1);
    return;
}

    // Recursively sort halves of dest into src
    int destLow  = low;
    int destHigh = high;
    low  += off;
    high += off;
    int mid = (low + high) >> 1;
    mergeSort(dest, src, low, mid, -off, c);
    mergeSort(dest, src, mid, high, -off, c);

    // If list is already sorted, just copy from src to dest.  This is an
    // optimization that results in faster sorts for nearly ordered lists.
    if (c.compare(src[mid-1], src[mid]) <= 0) {
       System.arraycopy(src, low, dest, destLow, length);
       return;
    }

    // Merge sorted halves (now in src) into dest
    for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
        if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
            dest[i] = src[p++];
        else
            dest[i] = src[q++];
    }
}

Upvotes: 3

Dave Costa
Dave Costa

Reputation: 48111

It is clearly an improper Comparator implementation. For instance, the Javadoc says that:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

That's obviously not true in this case, since it can return 1 but not -1.

I believe the reason that it does not cause an issue when sorting is that, with a standard comparator, two elements in a list are in an acceptable order if the compare method returns -1 or 0, but they must be swapped if it returns 1. So at least for some sort algorithms, it must be sufficient to correctly indicate whether the second argument is greater than the first.

Upvotes: 1

Jesper
Jesper

Reputation: 206796

It works by chance; the fact that it works depends on the implementation details of Collections.sort(). Since the comparator is not doing what it should actually do according to its contract, you cannot be sure that it will continue to work on other JVM implementations or even other versions of Oracle's JVM.

It doesn't make much sense to try to find out why it happens to work.

Upvotes: 3

Jon Skeet
Jon Skeet

Reputation: 1500275

It doesn't work for me. It produces the output of:

[10, 9, 8, 1, 2, 3, 7, 4, 5, 6]

(which is the same as the input order). That's not guaranteed though... I suspect it happens to have picked elements which are either already in the right order, or it decides they're "equal" and leaves them alone.

Note that o1 - o2 is also broken... consider if o1 = Integer.MIN_VALUE and o2 = 1... you could fix that by converting to long values first, of course.

A more natural implementation would be

return o1.compareTo(o2);

or:

int i1 = o1.intValue();
int i2 = o2.intValue();
return i1 < i2 ? -1 : i1 == i2 ? 0 : 1;

Upvotes: 7

Related Questions