¿Cómo determinar si una lista está ordenada en Java?

Me gustaría un método que tome una List donde T implemente Comparable y devuelva true o false dependiendo de si la lista está ordenada o no.

¿Cuál es la mejor manera de implementar esto en Java? Es obvio que generics y comodines están destinados a ser capaces de manejar tales cosas fácilmente, pero me estoy enredando.

También sería bueno tener un método análogo para verificar si la lista está en orden inverso.

Guava proporciona esta funcionalidad a través de su increíble clase de pedidos . Un Ordering es un Comparator ++. En este caso, si tiene una lista de algún tipo que implemente Comparable , podría escribir:

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

Esto funciona para cualquier Iterable , no solo List , y puede manejar null s fácilmente especificando si deben aparecer antes o después de cualquier otro elemento no null :

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

Además, dado que mencionó que le gustaría poder verificar el orden inverso tan bien como lo haría normalmente, eso se haría como:

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

Usuarios de Java 8 : utilice los Comparators#isInOrder(Iterable) equivalentes Comparators#isInOrder(Iterable) lugar, ya que el rest de los pedidos está casi obsoleto (como se explica en la documentación de la clase).

Aquí hay un método genérico que hará el truco:

 public static > boolean isSorted(Iterable iterable) { Iterator 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; } 

Fácil:

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

O (si los elementos son comparables):

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

O (si los elementos no son comparables):

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

Las implementaciones fallan para listas que contienen valores nulos. Tienes que agregar cheques apropiados en este caso.

Si está utilizando Java 8, las transmisiones pueden ayudar.

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

Este código clasificará la lista fuera de lugar y recogerá sus elementos en otra lista, que luego se comparará con la lista inicial. La comparación será exitosa si ambas listas contienen los mismos elementos en posiciones iguales.

Este método puede no ser la solución de más rápido rendimiento, pero es el más fácil de implementar, que no involucra marcos de terceros.

Para verificar si una lista o cualquier estructura de datos para ese asunto es una tarea que solo toma O (n) tiempo. Simplemente itere sobre la lista usando la Interfaz del Iterator y ejecute los datos (en su caso, ya lo tiene listo como un tipo de Comparable) de principio a fin y puede encontrar si está ordenado o no fácilmente

Simplemente use el iterador para revisar los contenidos de la 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; } 

Esto es lo que haría:

 public static > boolean isSorted(List list) { if (list.size() != 0) { ListIterator 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; } 
 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 no estoy seguro chicos lo que ustedes están haciendo, pero esto se puede hacer en simple para bucle.

Esta es una operación que tomará O (n) el tiempo (el peor caso). Necesitará manejar dos casos: donde la lista está ordenada en orden descendente y donde la lista está ordenada en orden ascendente.

Necesitará comparar cada elemento con el siguiente elemento mientras se asegura de que la orden se conserve.

Una implementación simple en arreglos:

 public static > boolean isSorted(T[] a, int start, int end) { while (start0) return false; start++; } return true; } 

Conversión para listas:

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

Si lo necesita para pruebas unitarias, puede usar AssertJ . Contiene una afirmación para verificar si una lista está ordenada:

 List someStrings = ... assertThat(someStrings).isSorted(); 

También hay un método alternativo que se isSortedAccordingTo eso toma un comparador en caso de que desee utilizar un comparador personalizado para la clasificación.