Is the term "natural ordering" specific to Java?

Question

The tutorial Object Ordering refers to the concept of "natural ordering":

If the List consists of String elements, it will be sorted into alphabetical order. If it consists of Date elements, it will be sorted into chronological order. How does this happen? String and Date both implement the Comparable interface. Comparable implementations provide a natural ordering for a class, which allows objects of that class to be sorted automatically. The following table summarizes some of the more important Java platform classes that implement Comparable.

Is the term "natural ordering" specific to Java, or language-independent? For example, could I talk about "natural ordering" in Ruby?

(Note: I'm not talking about Natural sort order, mentioned in Jeff Atwood's blog post Sorting for Humans : Natural Sort Order)

Answer 1

This is not a reference to the type of natural ordering where numbers inside of strings are sorted "naturally" instead of lexicographically digit-by-digit. Java defines the term differently.

Let's change the emphasis:

Comparable implementations provide a natural ordering for a class, which allows objects of that class to be sorted automatically.

The word "natural" means that if you implement Comparable then users of your class can sort it easily without needing a custom comparator. The sorting is natural; it's built in; it's free, no thinking required.

Is the term "natural ordering" specific to Java, or language-independent?

Yes. No. Both? It's specific to Java insofar as the documentation italicizes the term and there is a naturalOrder method. The concept is applicable to other languages, though, sure.

For example, could I talk about "natural ordering" in Ruby?

You could. If you were talking off the cuff you could use the term. If you were writing formally it would be prudent to define it. Because of the confusion with Atwood's use of the term, I'd prefer a different one. Say, "default ordering".

Answer 2

I believe the term has a specific meaning in Java

At least in the official documentation.

From the API doc for the 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.

If we are very familiar with this line from the API doc. Then we see a class implements the Comparable interface, and we see somewhere/somebody mentions the "natural order" of two instances of A, we know that it might be talking about the order imposed by the compareTo method. The question is, does the person saying/writing that term also knows about this specific meaning and is using it in the context?

Of course the API doc is using the term that way because the first thing it does is to define it.

Answer 3

No, the term natural ordering is not Java specific. My opinion is it doesn't pertain to programming languages specifically at all; rather, likely all programming languages (although they may or may not use the term explicitly) rely on the concept.

For example, how would a method like max(a, b) or a.after(b) work if there wasn't a concept of natural ordering? We know the natural order of integers: 1, 2, 3, ...; dates 1/1/1990, 1/2/1990, 1/1/1991, ...; time: 12:00, 12:01, 1:01 ... These system are human-defined but it's what we expect. If we had a number of integers ordered 1, 3, 2, 4 it would be unnatural.

Your quote, as I read it, suggests just that. A type that implements the Comparable interface provides a "default", well-defined, or expected ordering. For developer-defined types it's up to the developer to enforce the natural ordering (as Java developers did with Numbers) or define the natural ordering as we often do with complex types of our own.

When a class implements the Comparable interface it provides a compile-time (natural) ordering only to be altered by providing a custom Comparator. Still, there are a limited number of objects or systems we can represent in software that have a true, well-understood, and accepted natural order. Many types like Students, Cars, and Users can depend on one or a combination of attributes that determine their order which may not seem natural at all.

Answer 4

This can be achieved by implementing new Comparator<String> and pass it to Collections.sort(list, comparator) method.

@Override
public int compare(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int lim = Math.min(len1, len2);
    char v1[] = s1.toCharArray();
    char v2[] = s2.toCharArray();

    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            if(this.isInteger(c1) && this.isInteger(c2)) {
                int i1 = grabContinousInteger(v1, k);
                int i2 = grabContinousInteger(v2, k);
                return i1 - i2;
            }
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

private boolean isInteger(char c) {
    return c >= 48 && c <= 57; // ascii value of 0-9
}

private int grabContinousInteger(char[] arr, int k) {
    
    int i = k;
    while(i < arr.length && this.isInteger(arr[i])) {
        i++;
    }
    return Integer.parseInt(new String(arr, k, i - k));
}