why we need to return 0 when Comparator.compare become equal

user_5635833 0
Viewed 6335

I understand that when implement compare method of Comparator interface we need to return

  • +1 if o1 > o2
  • -1 if o1 < o2
  • 0 if o1 == o2

my question is why we need to return 0 when both equal? what is the use case or where it being used? if we considered sorting when o2 greater than to o1 or o2 equal to o1 does not change it place. can anyone come explain practical use case for this?

Java documentation says

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.

Does this mean return -1 or return 0 has same impact?

zero, or a positive integer 

 @Override
    public int compare(Test f1, Test f2) {
        if (f1.getId() > f2.getId()) {
            return 1;
        } else if (f1.getId() < f2.getId()) {
            return -1;
        } else {
            return 0;
        }

    }
comparator collections sorting java
3 Answers

If you return -1 when the two values being compared are equal, compare(f1,f2) and compare(f2,f1) will both return -1. This means that the ordering of your elements will not be consistent. It can break some sorting algorithms.

That's why the general contract of compare requires that:

sign(compare(f1,f2)) = -sign(compare(f2,f1))

which means you must return 0 when the two values are equal.

user_12215710

When you are sorting, -1 and 0 essentially have a very similar impact on the ordering of the sorted list as items where the compareTo evaluate to 0 will just be grouped together.

You would "practically" use this comparison in other scenarios, such as where you may not want to duplicate the adding of complex objects to a list (yes, you could also achieve this scenario through the use of a set as well).

Say we have an object Book as follows:

import java.util.Comparator;

public class Book implements Comparable {

  String isbn;
  String title;

  public Book(String id, String title) {
    this.isbn = id;
    this.title = title;
  }

  String getIsbn() {
    return isbn;
  }

  String getTitle() {
    return title;
  }

  @Override
  public int compareTo(Object o) {
    return Comparator
            .comparing(Book::getIsbn)
            .thenComparing(Book::getTitle)
            .compare(this, (Book) o);
  }

  @Override
  public  String toString() {
    String output = new StringBuilder()
            .append(isbn).append(":").append(title)
            .toString();
    return output;
  }
}

Here we have overridden the compareTo of book to create a custom comparison that first checks the books isbn and then it's title.

Say (for example) you have a library, that has books in it. You may want to prevent your user from adding duplicate books in that library ... 

public class Library {

  public static void main(String [] args) {
    List<Book> library = new ArrayList<>();
    library.add(new Book("9780593098240", "Children of Dune"));
    library.add(new Book("9780593098233", "Dune Messiah"));
    library.add(new Book("9780441172719", "Dune"));
    // Just to show the sorting, based on multiple attributes.
    Collections.sort(library);
    System.out.println("Books in library: " + Arrays.toString(library.toArray()));

    // You would obviously have some code for entering a book here, but easier to just create the object for an example. 
    Book newBook = new Book("9780593098240", "Children of Dune");
    for (Book bookInLibrary : library) {
        if (bookInLibrary.compareTo(newBook) == 0) {
            System.out.println("We already have that book in the library.");
            break;
        }
    }
  }
}
user_120891830

You can think about Binary search algorithm with the following implementation: 

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

Suppose there is a Comapator which returns same value for equal and less cases:

public int compare(Test f1, Test f2) {
        if (f1.getId() > f2.getId()) {
            return 1;
        } else {
            return -1; 
}

Now A[m] < T or A[m].compareTo(T) < 0, will be true when T is equal to A[m] and when A[m] is less then T.

So in the this situation:

1 2 3 4 // array and A[m] is 2
2 // target T

2.compareTo(2) returns -1 which makes algorithm to go to the next execution L = m + 1 -> instead of returning correct value.

In fact binary search will get stuck in an infinitive loop, jumping from 2.compareTo(2) and 3.compareTo(2). I hope this helps.

user_64407040
Related