Standard function for checking sorted-ness

Question

I have, in Java, a Double[] foo.

Is there a library function for telling me if this array is sorted? I know I can build such a function but that's not a good thing to do if a library function is available. There's nothing in java.util.Arrays and seemingly nothing in java.util.Collections.

(In C++ we have std::is_sorted and given that the Java library is even bigger than C++11 I imagine there's something there I can use).

You asked a very similar question here: http://stackoverflow.com/questions/26527771/minimum-element-of-an-array — Maroun, Oct 23 '14 at 13:22
Indeed I did. If I ask two questions in one question then another faction of this site will penalise you. I studied the answer to that question - you see in this one that I now mention `java.util.Collections`. — P45 Imminent, Oct 23 '14 at 13:24
If there is some issue with my asking another but indeed related question, then do tell me citing appropriate SO guidelines. — P45 Imminent, Oct 23 '14 at 13:25
@SlodgeMonster Don't think people here have an issue with 2 related questions in one post. You have an example of this happening? — Grice, Oct 23 '14 at 13:29

OldCurmudgeon · Answer 1 · 2014-10-23T15:13:18.683

As far as I know there is no such function.

It may be worth noting that it could actually take no more time to sort it than to determine whether it is sorted or not.

You could always wrap it in an object that maintains a sorted flag for you.

You could implement the function yourself quite efficiently using:

/**
 * Bridge function to the isSorted(Iterable<Comparable>) below
 * allowing arrays to tested too.
 * 
 * @param <T> - The elements in the array.
 * @param a - The array.
 * @return - true if the Array is sorted - false otherwise.
 */
public static <T extends Comparable<T>> boolean isSorted(T[] a) {
    return isSorted(Arrays.asList(a));
}

/**
 * Checks sortedness of any Iterable of Comparables.
 * 
 * @param <I> - The type of the Iterable.
 * @param <T> - The type of the Comparable.
 * @param a - The Iterable<Comparable> to test.
 * @return - true if the Iterable is sorted - false otherwise.
 */
public static <T extends Comparable<T>> boolean isSorted(Iterable<T> a) {
    // Remember the previous element.
    T prev = null;
    for (T it : a) {
        if (prev != null && it.compareTo(prev) < 0) {
            // This should be before prev! Not sorted!!
            return false;
        }
        prev = it;
    }
    // All in order.
    return true;
}

Checking sortedness is at worse, O(N). Sorting is at best O(N). — P45 Imminent, Oct 23 '14 at 13:29
@SlodgeMonster - Correct - and many sorting algorithms achieve O(N) when given sorted data - BubbleSort for example. — OldCurmudgeon, Oct 23 '14 at 13:36
He has a good point... how are you going to use it? `if (notSorted(array)) sort(array)` ? You might as well call sort on it without even checking. If it wasn't sorted, you are going to sort it anyway so the time checking is a waste. If it was sorted, it will be O(n) which is similar to the time to sort it to begin with. — grinch, Oct 23 '14 at 13:39
The type parameter `I` is obsolete. Just declare the parameter type as `Iterable`. The parameter will accept subtypes of `Iterable` anyway. — Holger, Oct 23 '14 at 14:42

score 0 · Answer 2 · answered Oct 23 '14 at 13:55

0

There doesn't seem to be a standard function. Use this:

private static <T extends Double/*Can't extend Number for some reason ;-)*/>
boolean isSorted(T[] x)
{
    if (x != null){
        for (int n = 1; n < x.length; ++n){
            if (x[n - 1] >= x[n]){
                return false;
            }
         }
    }
    return true;            
}

answered Oct 23 '14 at 13:55

P45 Imminent

8,319
4
35
78

You could use `T extends Comparable`. – OldCurmudgeon Oct 23 '14 at 14:09
@OldCurmudgeon exactly what i was going to say. – will Oct 23 '14 at 14:55

Standard function for checking sorted-ness

2 Answers2