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

Question

Me gustaría un método que toma List<T> donde T implementa Comparable y devuelve 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 genéricos 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.

Answer 1

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

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

Esto funciona para cualquier Iterable, no sólo List, y que puede manejar null s fácilmente especificando si deben venir antes o después de cualquier otro null elementos no:

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

también, ya que ha mencionado que le gustaría ser capaz de comprobar el orden inverso, así como de costumbre, que se llevaría a cabo como:

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

Java 8 usuarios: Utilice el equivalente Comparators#isInOrder(Iterable) lugar, ya que el resto de pedidos es en su mayoría obsoletos (como se explica en la clase documentation).

Answer 2

Para comprobar si una lista o cualquier estructura de datos para esa materia es una tarea que solo toma O (n) tiempo. Simplemente itere sobre la lista usando la interfaz 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

Answer 3

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

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

Answer 4

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 fracasan por listas que contienen valores nulos. Tienes que agregar cheques apropiados en este caso.

Answer 5

Simplemente use el iterador para revisar los contenidos del 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 6

Esto es lo que haría:

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 7

Aquí es un método genérico que va a hacer el truco:

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 8

Una aplicación sencilla en 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; 
} 

la conversión de listas:

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 9

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 no estoy seguro de lo que ustedes están haciendo, pero esto se puede hacer en bucle simple.

Answer 10

Si lo necesita para probar la unidad, puede usar AssertJ. Contiene una afirmación para comprobar si se ordena una lista:

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

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

Answer 11

Si está utilizando Java 8, las secuencias pueden ser de ayuda.

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

Este código será ordenar la lista fuera de lugar y recoger sus elementos en otra lista, que luego se compara 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 la más fácil de implementar, que no implica marcos de terceros.