How to determine if a list is sorted in Java?

Question

I need 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 designed to work with such things easily, but I'm confused.

It would be nice to have a similar method to check if the list is in reverse order.

Answer 1

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

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

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

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

In addition, since you mentioned that you want to check the reverse order as well as the normal one, this will be done as:

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

Java 8 users . Instead, use the equivalent Comparators#isInOrder(Iterable) as the rest of the order is mostly out of date (as explained in the class documentation ).

Answer 2

Here is a general 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; } 

Answer 3

Easily:

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

Or (if the elements are comparable):

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

Or (if the elements are not comparable):

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

Implementations are not performed for lists containing null values. You must add appropriate checks in this case.

Answer 4

If you are using Java 8, threads can help.

 list.stream().sorted().collect(Collectors.toList()).equals(list); 

This code sorts the list inappropriately and collects its elements in another list, which is then compared with the original list. Comparison will be successful if both lists contain the same elements in equal positions.

This method may not be the fastest solution, but it is easiest to implement, which is not related to third-party structures.

Answer 5

To check if a list or some data structure is in this case a task that takes only O (n) time. Just iterate over the list using the Iterator interface and skip the data (in your case, you already have it ready as a Comparable type) from beginning to end, and you can find out if it is sorted or not.

Answer 6

Just use an iterator to view the contents of 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; } 

Answer 7

 private static <T extends Comparable<? super T>> boolean isSorted(List<T> array){ for (int i = 0; i < array.size()-1; i++) { if(array.get(i).compareTo(array.get(i+1))> 0){ return false; } } return true; } 

zzzzz is not sure guys what you are doing, but it can be done in a simple for loop.

Answer 8

If you need it for unit testing, you can use AssertJ . It contains a statement to check the sorting of the list:

 List<String> someStrings = ... assertThat(someStrings).isSorted(); 

There is also an alternative isSortedAccordingTo method that accepts a comparator if you want to use your own sorter for sorting.

Answer 9

This is an operation that takes 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, making sure that the order is preserved.

Answer 10

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; } 

Answer 11

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; } 

Convert to 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; } 

Answer 12

Here is a method using Iterable and Comparator .

 <T> boolean isSorted(Iterable<? extends T> iterable, Comparator<? super T> comparator) { boolean beforeFirst = true; T previous = null; for (final T current : iterable) { if (beforeFirst) { beforeFirst = false; previous = current; continue; } if (comparator.compare(previous, current) > 0) { return false; } previous = current; } return true; } 

And the method for Iterable of Comparable and the flag for ordering.

 <T extends Comparable<? super T>> boolean isSorted( Iterable<? extends T> iterable, boolean natural) { return isSorted(iterable, natural ? naturalOrder() : reverseOrder()); } 

Answer 13

Using Java 8 threads:

 boolean isSorted = IntStream.range(1, list.size()) .map(index -> list.get(index - 1).compareTo(list.get(index))) .allMatch(order -> order <= 0); 

This also works for empty lists. However, it is only effective for lists that also have a RandomAccess token RandomAccess (for example, ArrayList ).

If you don’t have access to the stream underlying the collection, you can use the following ugly hack:

 Stream<T> stream = ... Comparator<? super T> comparator = ... boolean isSorted = new AtomicInteger(0) {{ stream.sequential() .reduce((left, right) -> { getAndUpdate(order -> (order <= 0) ? comparator.compare(left, right) : order); return right; }); }}.get() <= 0;