What's the difference between natural ordering and total ordering?

Question

I happen to come across many statements like Comparable is used when natural ordering is required while sorting an array or collection and Comparator for total ordering.

The version you may have heard could be same or different with the same meaning but ultimately its one of the distinguishing factors between the two (Comparator and Comparable interfaces).

But, I couldn't find a difference between the two types of ordering anywhere. I'd appreciate if someone could explain it with a good example :)

Answer 1

Simple answer: There is no natural order in Java.

If a class (like many do) implements java.util.Comparable the compareTo method defines the order of the instances and we can use e.g. java.util.Arrays.sort. If the class does not provide the compareTo method the order is undefined and java.util.Arrays.sort gives Runtime java.lang.ClassCastException: ... cannot be cast to java.lang.Comparable. Because allmost all(?) classes implement java.util.Comparable this appears to be their natural order.

Answer 2

Total ordering means all values can be compared to all other values. For example, if you have a collection of BigDecimal and String there is no natural total order (but you could invent one)

In Java, the Natural order is defined as the ordering provided by the JVM. This might not match what a people might believe is the natural order. e.g. Strings are sorted ASCIIbetically. Meaning an uppercase Z comes before a lowercase a and 10 is before 2

http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

Answer 3

Comparable implementations provide a natural ordering for a class, which allows objects of that class to be sorted automatically. (Ref: https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html)

Implementation of the Comparable interface enforces total ordering or the ability to sort the entire array from beginning to end.

Answer 4

To elaborate on @Bruno's answer: an example of a partial ordering is the divisibility relation between positive numbers. If you compare 5 and 15, you can say that 5 is a divisor of 15, and 15 is the multiple of 5. However, 3 and 5 are not comparable because 3 is neither the divisor nor the multiple of 5.

An example of total ordering is the less than relation, because if you take any two different numbers, one of them is less than the other. So any value is comparable with any other value.

On the concept of natural ordering: If the objects of a type have a really-really obvious way to be sorted, than it is the natural ordering. For example, the natural ordering of Strings is the alphabetical order, and the natural order of numbers is ascending order, because it is the first choice anybody would think of. However, sometimes you would want to order Strings in a different way, e.g. sorting by length from the 1-character ones to the longer ones. This is a possible total ordering on Strings, but not the natural one.

Not all objects necessarily have a natural ordering. E.g. if you have Person objects, sorting them by height is a possible total ordering, but so is sorting them by age... None of these are more obvious than the other, this is why there is no natural ordering.

Answer 5

Important point: natural ordering should be consistent with equals!

Summary: natural ordering is one kind of total ordering which is default (used the most often) for the given class and is consistent with equals. Total ordering is any ordering where all values can be compared to all other values.

e.g. when you design new class then you can choose the natural ordering inside the class. Any other ordering can be then only the total one ;)

Answer 6

Natural Order

It depends on our collections that we use, for example, say, we have characters object, then natural order is their unicode values, for numbers natural order is as usual, ascending order

Comparable Interface- This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this interface can be used as keys in a sorted map or elements in a sorted set, without the need to specify a comparator.

public interface Comparable<T> {

    /**
     * Compares this object with the specified object for order.  Returns a
     * negative integer, zero, or a positive integer as this object is less
     * than, equal to, or greater than the specified object.
     */
    public int compareTo(T o);
}

Comparator Interface:

This interface Represents an order relation, which may be used to sort a list or maintain order in a sorted set or map. Can override a type's natural ordering, or order objects of a type that does not implement the Comparable interface.

A comparison function, which imposes a total ordering on "some collection of objects". Comparators can be passed to a sort method (such as Collections.sort) to allow precise control over the sort order. Comparators can also be used to control the order of certain data structures (such as TreeSet or TreeMap).

    public interface Comparator<T> {
    /**
     * 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.
     */
    int compare(T o1, T o2);

    boolean equals(Object obj);
}

Hope This helps you.                    

Answer 7

Total ordering is a general mathematical concept. It differs mainly from partial ordering in that for each a and b in set X, either "a <= b" or "b <= a" are meaningful and true. As far as Java is concerned, this means that of two Comparable instances, one must be greater or equal than the other (i.e. it makes sense to compare them).

Answer 8

Natural ordering is a default total ordering. This is the only difference between the two.