How to determine if a List is sorted in Java?
I would like a method that takes a List
14 Answers 14
Guava provides this functionality through its Comparators class.
boolean sorted = Comparators.isInOrder(list, comparator); There’s also the Ordering class, though this is mostly obsolete. 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 null s 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); Can you show an example of this if there is no natural ordering and you want to pass in a Comparator ? I think that’s what Ordering.from is for: «Returns an ordering based on an existing comparator instance. Note that it is unnecessary to create a new anonymous inner class implementing Comparator just to pass it in here. Instead, simply subclass Ordering and implement its compare method directly.»
@tieTYT: You can using Ordering.from(comparator).isOrdered(list) ; if you’re implementing the comparator yourself, though, you might as well just extend Ordering rather than implementing Comparator to begin with, in which case it’s just myOrdering.isOrdered(list) .
Just leaving a note here. Most of ordering is Obsolete but they removed the comments for planned deletion here. github.com/google/guava/commit/…
Stream
If you are using Java 8 or later, streams may be able to help.
list.stream().sorted().collect(Collectors.toList()).equals(list); list.stream().sorted().toList().equals(list); This code will sort the list out of place and collect its elements in another list, which is then compared to the initial list. The comparison will be successful, if both lists contain the same elements in equal positions.
Note that this method will have worse space and time complexity than other approaches because it will have to sort the list out of place, so it should not be used for very large lists. But it is the easiest to use because it is a single expression and does not involve 3rd party libraries.
According to Java 8 docs, Collectors.toList(); There are no guarantees on the type, mutability, serializability, or thread-safety of the <@code List>returned; You should use a supplier of ArrayList
It does not look like this is relevant for this case, as the generated list never outlives is statement, so it will never be serialized, mutated or accessed from multiple threads.
Here’s a generic method that will do the trick:
public static > boolean isSorted(Iterable iterable) < Iteratoriter = 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; > List tmp = new ArrayList(myList); Collections.sort(tmp); boolean sorted = tmp.equals(myList); Or (if elements are comparable):
Object prev = null; 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 = null; 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.
Collections.sort would require that the list elements be comparable already, and that was a stipulation in the question in any event.
The first example is also pretty wasteful for what it does, and the Objects in the second need to be Comparable.
If you need it for unit testing, you can use AssertJ. It contains an assertion to check if a List is sorted:
List someStrings = . assertThat(someStrings).isSorted(); There is also an alternative method isSortedAccordingTo that takes a comparator in case you want to use a custom comparator for the sorting.
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
-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.
private static > boolean isSorted(List 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 not sure guys what you guys are doing but this can be done in simple for loop.
fwiw, the implementation of the library in the accepted answer (Guava) is essentially this: github.com/google/guava/blob/… But IMO it’s always better to keep your codebase small rather than reimplementing things a library can give you.
Simply use the iterator to look through the contents of the List .
public static boolean isSorted(List listOfT) < T previous = null; for (T t: listOfT) < if (previous != null && t.compareTo(previous) < 0) return false; previous = t; >return true; > @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.
I’ve accepted the solution that avoids using raw types. This was my second choice, though, so I’ve upvoted it.
boolean isSorted = IntStream.range(1, list.size()) .map(index -> list.get(index - 1).compareTo(list.get(index))) .allMatch(order -> order This also works for empty lists. It is however only efficient for lists that also implement the RandomAccess marker interface (e.g., ArrayList ).
If you do not have access to the stream's underlying collection, the following ugly hack can be used:
Stream stream = . Comparator comparator = . boolean isSorted = new AtomicInteger(0) < getAndUpdate(order ->(order ); >>.get() 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.
public static > boolean isSorted(List list) < if (list.size() != 0) < ListIteratorit = 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; > It doesn't work. ``` public static void main(String[] args) < List
One simple implementation on arrays:
public static > boolean isSorted(T[] a, int start, int end) < while (start0) return false; start++; > return true; > public static > boolean isSorted(List a) < int length=a.size(); if (length<=1) return true; int i=1; T previous=a.get(0); while (i0) return false; previous=current; > return true; > 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.
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.
Here comes a method using an Iterable and a Comparator .
boolean isSorted(Iterable iterable, Comparator 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 a method for an Iterable of Comparable and a flag for ordering.
> boolean isSorted( Iterable iterable, boolean natural)
IMO, from what I'm seeing, the complexity of checking this is as bad as performing the sort for a second time, and I understand people are short circuiting with returns if it is not sorted, but if the List is actually sorted, then the entire length will be traversed. I'd argue to just let the code continue as if the List was sorted, and let the code itself figure out if it is or not.
I would recommend placing an Error detailing why the specific line that will fail is doing so because its collection is not reversed/ordered etc.
the line detachTailIndex.run() will give a NullPointerException(),
if (fromReversedMethod && detachTailIndex == null) < throw new NullPointerException("detachTailIndex was null. \n Reason: The List<>is required to be reversed before submission") > Or if your plan is to use a conditional for when sorted or not the you can use the null to verify if it is sorted and choose the other option.
If there is no other option, then using the other responses are ok.
int key = entry.getKey(); List shouldBeReversed = entry.getValue(); try < //If all entries need to be iterated better place them inside the Try-Catch updateBatch(key, xes -> < for (int rowIndex : shouldBeReversed ) < xes.remove((int) rowIndex); // will return an IndexOutOfBoundsException if not sorted in reverse >return xes; > ); > catch (IndexOutOfBoundsException e) < throw new IndexOutOfBoundsException(e.getMessage() + "\n" + "Reason: Batch indexes (Entry's value \"List\") should be sorted in reverse order before submission"); > if conditional is required (on sorted, or on not sorted) then the catch() body could be used as a "not sorted" option.
Of course this is very very case specific, but seems that checking for a sorting order just to get a boolean seems too much (?) specially on iterations.
What is the difference between an ordered and a sorted collection?
Do not take the answers here too literally. While that is the kind of definition widely understood & acknowledged, its not the de facto definition in computer terminology. For eg, in .NET the interface for "sorted" enumerable is called IOrderedEnumerable (funny thing is its not very consistent in .NET. An "insertion order" respectin dictionary in .NET is called OrderedDictionary which some believe is a misnomer as compared to say, IndexedDictionary ). Yes in java world (mostly elsewhere too) they mean what u've in answers. For more see here.
If some implementation instance gets the naming wrong, that's no reason to propagate its error. It's a good question, with good answers. Use proper naming - helps reducing confusion for everybody, including yourself.
8 Answers 8
An ordered collection means that the elements of the collection have a specific order. The order is independent of the value. A List is an example.
A sorted collection means that not only does the collection have order, but the order depends on the value of the element. A SortedSet is an example.
In contrast, a collection without any order can maintain the elements in any order. A Set is an example.
@overexchange Given the above definitions, a priority queue would be a sorted collection in most cases, since the priority is almost always defined as a property of the elements in the queue.
If SortedSet has inherited from Set and is having a is-a relationship with it then how can u say Set is without any order
An ordered collection maintains the order of the elements based on the sequence you put stuff into/remove them from the collection.
A sorted collection keeps the elements sorted based on a sort criteria.
Java uses "ordered collection" to mean a collection such as List, where (unlike HashSet), the collection remembers what order the elements are supposed to be in. So elements can be added to the collection at a particular "place" in the order.
Java uses "sorted collection" to mean a collection such as SortedSet, where (unlike List), the order that the iterator traverses the collection is in accordance with a specified Comparator or the natural order of the elements.
So the difference is whether the ordering depends on the values ("sorted"), or is a property that elements have independently of their value ("ordered").
Good answer and +1 for mentioning "Java". Its kinda the accepted definition in most places too, like OrderedDict in python. But in .NET the interface for "sorted" enumerable is called IOrderedEnumerable . So it depends. Just saying..
Yes, though the concepts are similar.
List is an ordered collection: each element has an index, which forms an ordering of the elements, but not usually related to any property of the elements themselves.
SortedMap and SortedSet are sorted collections, which means that iteration through the collection will happen in a sequence derived from the elements themselves. For example, if you have a SortedSet then the Strings will be sorted according to the lexicographical sort order.
An ordered Collection can be sorted but doesn't have to be (e.g. after using Collections.sort() ) when the external ordering is identical with the elements' sort order. A sorted collection is always implicitly ordered (i.e. there is always a "first" element, and it's always the same as long as you don't add another, smaller one).