CODEWITHSUNDEEP
javasortingcollectionsjava-8comparator
Govan
Govan

Reputation: 2129

Collections.sort in java 8 is not working as java 6 while comparator returning 0

Recently I updated our application jdk from Java 6 to Java 8 but kept source language level still as Java 6. After change one of our unit tests was failing. I noticed that Collections.sort for LinkedList is working different in Java 8 and Java 6. Even when I am Source Level java 8 with JDk 1.8 I am getting same different behavior. To recreate problem: Defining the enum below: 

public enum Weight {
    A(1), B(0), C(0), D(0), E(2);

    public int getWeight() {
        return weight;
    }

    private int weight;

    Weight(int weight) {

        this.weight = weight;
    }

    @Override
    public String toString() {
       return  name() + '(' + weight + ')';
    }
}

and a main Class as below: 

public class Main {

    public static void main(String[] args) {
      List<Weight> weightList = new LinkedList<Weight>();
      weightList.add(Weight.A);
      weightList.add(Weight.B);
      weightList.add(Weight.C);
      weightList.add(Weight.D);
      weightList.add(Weight.E);

        Collections.sort(weightList, new Comparator<Weight>() {
            @Override
            public int compare(Weight o1, Weight o2) {
                return o1.getWeight() > o2.getWeight()? 1:0;
            }
        });

        System.out.print(weightList);

    }
}

The output for running the code under Java 6 is: "C:\Program Files\Java\jdk1.6.0_45\bin\java"

[B(0), C(0), D(0), A(1), E(2)]

and output for running code under java 8 is:

"C:\Program Files (x86)\Java\jdk1.8.0_161\bin\java"

[A(1), B(0), C(0), D(0), E(2)]

I changed the type from LinkedList to ArrayList and I am getting the same result but if I am changing the comparator as below then Java 8 is going to sort the array:

Collections.sort(weightList, new Comparator<Weight>() {
            @Override
            public int compare(Weight o1, Weight o2) {
                return o1.getWeight() > o2.getWeight()? 1:-1;
            }
        });

As you see it seems that the java 8 is not sorting the code properly. Is there a bug in Java or am I missing something as usual?

Upvotes: 5

Views: 5824

Answers (3)

John Kugelman
John Kugelman

Reputation: 361585

public int compare(Weight o1, Weight o2) {
    return o1.getWeight() > o2.getWeight()? 1:0;
}

This definition doesn't meet the contract expected by the Java API. sort's behavior is undefined if you pass it an invalid Comparator.

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

  • The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

  • Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

Your function doesn't return -1 if o1 < o2. It returns 0, incorrectly asserting that the arguments are equal. This also causes it to fail the first bullet: if you flip the arguments, the result needs to change sign.

A correct implementation would be:

public int compare(Weight o1, Weight o2) {
    return Integer.compare(o1.getWeight(), o2.getWeight());
}

Upvotes: 11

davidxxx
davidxxx

Reputation: 131316

As Boris suggested in its comment : your compare() method is not correct.

Look at your implementation :

 return o1.getWeight() > o2.getWeight()? 1:0;

Suppose you have three objects in your list:

  • o1 : weigth 3
  • o2 : weigth 5
  • o3 : weigth 5

Now suppose that sort() invokes compare() in this way for your list :

compare(o1, o2) returns 0

compare(o2, o3) returns 0

By transitivity, it means that o1, o2 and o3 have the same order. You don't want that I assume.
If it works on Java 6, it's simply "chance" in the implementation and not a result that you should reliably expect to.

To solve your issue, you have to handle the 3 cases (superior, inferior or equal) : 

@Override
public int compare(Weight o1, Weight o2) {
    if (o1.getWeight() > o2.getWeight()){
        return 1;
    }
    else if (o1.getWeight() < o2.getWeight()){
        return -1;
    }
    return 0;
}

Which is equivalent finally to write : return Integer.compare(o1.getWeight(), o2.getWeight()).

Note that a much better alternative and less error prone in Java 8 is using the Comparator.comparingInt() factory method and used directly the sort() method that was introduced in List:

weightList.sort(Comparator.comparingInt(Weight::getWeight));

Upvotes: 5

fps
fps

Reputation: 34460

The internal sort algorithm was changed to Tim Sort for objects and a dual-pivot quicksort for primitives as from JDK 7.

As your comparator was wrong (it was returning 0 for non-equal values), you were very lucky that it didn't break before. Now it breaks as expected.

Upvotes: 15

Related Questions