views:

246

answers:

8

I would like a method that takes a List<T> where T implements Comparable and returns true or false depending on whether the list is sorted or not.

What is the best way to implement this in Java? It's obvious that generics and wildcards are meant to be able to handle such things easily, but I'm getting all tangled up.

It would also be nice to have an analogous method to check if the list is in reverse order.

+4  A: 

To check whether a list or any data structure for that matter is a task that only takes O(n) time. Just iterate over the list using the Iterator Interface and run through the data (in your case you already have it ready as a type of Comparable) from start to end and you can find whether its sorted or not easily

Bragboy
Interestingly, your algorithm is actually O(1) expected time for reasonably random lists.
mikera
It would be O(n) in the worst case (when the list is indeed sorted).
Jesper
-1 since the asker has indicated he's getting "tangled up" in implementation issues like generics and wildcards, I think this answer is only telling him things he already knows.
Kevin Bourrillion
+1  A: 

This is an operation that will take O(n) time (worst case). You will need to handle two cases: where the list is sorted in descending order, and where the list is sorted in ascending order.

You will need to compare each element with the next element while making sure that the order is preserved.

Vivin Paliath
+2  A: 

Easy:

List tmp = new ArrayList(myList.size());
Collections.sort(tmp);
boolean sorted = tmp.equals(myList);

Or (if elements are comparable):

Object prev;
for( Object elem : myList ) {
    if( prev != null && prev.compareTo(elem) > 0 ) {
        return false;
    }
    prev = elem;
}
return true;

Or (if elements are not comparable):

Object prev;
for( Object elem : myList ) {
    if( prev != null && myComparator.compare(prev,elem) > 0 ) {
        return false;
    }
    prev = elem;
}
return true;

The implementations fail for lists containing null values. You have to add appropriate checks in this case.

Daniel
Collections.sort would require that the list elements be comparable already, and that was a stipulation in the question in any event.
Yishai
I think your first example is missing a line, since `tmp` is not populated.
FarmBoy
The first example is also pretty wasteful for what it does, and the Objects in the second need to be Comparable.
ColinD
+1 @Farmboy: Good catch
Daniel
+3  A: 

Simply use the iterator to look through the contents of the List<T>.

public static <T extends Comparable> boolean isSorted(List<T> listOfT) {
    T previous = null;
    for (T t: listOfT) {
        if (previous != null && t.compareTo(previous) < 0) return false;
        previous = t;
    }
    return true;
}
jjnguy
This keeps continuing because `previous` will never be set. See answer of Daniel for right flow.
BalusC
Oops, thanks for pointing that out. I fixed it. (@BalusC)
jjnguy
Would need to be constrained to `<T extends Comparable>` as well of course.
ColinD
@Colin (and everyone else) I am sorry that this doesn't compile. I wrote it very quickly. Colin, you have edit power, feel free to fix this error I made.
jjnguy
I've accepted the solution that avoids using raw types. This was my second choice, though, so I've upvoted it.
FarmBoy
@FarmBoy, Thanks for the feed back! Glad we could help.
jjnguy
+5  A: 

Guava provides this functionality through its awesome Ordering class. An Ordering is a Comparator++. In this case, if you have a list of some type that implements Comparable, you could write:

boolean sorted = Ordering.natural().isOrdered(list);

This works for any Iterable, not just List, and you can handle nulls easily by specifying whether they should come before or after any other non-null elements:

Ordering.natural().nullsLast().isOrdered(list);

Also, since you mentioned that you'd like to be able to check for reverse order as well as normal, that would be done as:

Ordering.natural().reverse().isOrdered(list);
ColinD
And there is also `isStrictlyOrdered()` if you want to make sure there are no duplicates.
Kevin Bourrillion
+1 for pointing to existing code so that people stop reinventing things and start making new things.
JUST MY correct OPINION
+1  A: 

This is what I would do:

public static <T extends Comparable<? super T>> boolean isSorted(List<T> list) {
    if (list.size() != 0) {
        ListIterator<T> it = list.listIterator();
        for (T item = it.next(); it.hasNext(); item = it.next()) {
            if (it.hasPrevious() && it.previous().compareTo(it.next()) > 0) {
                return false;
            }
        }

    }
    return true;
}
Yishai
+4  A: 

Here's a generic method that will do the trick:

public static <T extends Comparable<? super T>>
        boolean isSorted(Iterable<T> iterable) {
    Iterator<T> iter = iterable.iterator();
    if (!iter.hasNext()) {
        return true;
    }
    T t = iter.next();
    while (iter.hasNext()) {
        T t2 = iter.next();
        if (t.compareTo(t2) > 0) {
            return false;
        }
        t = t2;
    }
    return true;
}
Sean
A: 

One simple implementation on arrays:

public static <T extends Comparable<? super T>> boolean isSorted(T[] a, int start, int end) {
    while (start<end) {
        if (a[start].compareTo(a[start+1])>0) return false;
        start++;
    }
    return true;
}

Converting for lists:

public static <T extends Comparable<? super T>> boolean isSorted(List<T> a) {
    int length=a.size();
    if (length<=1) return true;

    int i=1;
    T previous=a.get(0);
    while (i<length) {
        T current=a.get(i++);
        if (previous.compareTo(current)>0) return false;
        previous=current;
    }
    return true;
}
mikera
p.s. note the implementation is deliberately designed to avoid allocating an iterator or making multiple calls to get. This is designed for the common case where you are using an ArrayList, for other list implementation you are probably better off using the iterator.
mikera
One thing that could be done in this case would be to check if the `List` implements `RandomAccess` and use this implementation if so and an `Iterator` implementation if not. You wouldn't really want to use this with a `LinkedList` as is.
ColinD
@ColinD great idea! I'm guessing you could do this so that it detects this at compile as well
mikera