Come determinare se un elenco è ordinato in Java?

Vorrei un metodo che utilizzi un List dove T implementa Comparable e restituisce true o false seconda che l’elenco sia ordinato o meno.

Qual è il modo migliore per implementarlo in Java? È ovvio che generici e wildcard sono pensati per essere in grado di gestire facilmente queste cose, ma mi sto aggrovigliando.

Sarebbe anche bello avere un metodo analogo per verificare se l’elenco è in ordine inverso.

Guava fornisce questa funzionalità attraverso la sua fantastica class di ordini . Un Ordering è un Comparator ++. In questo caso, se hai un elenco di alcuni tipi che implementa Comparable , potresti scrivere:

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

Questo funziona per qualsiasi Iterable , non solo per List , e puoi gestire facilmente i null specificando se devono venire prima o dopo altri elementi non null :

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

Inoltre, dal momento che hai detto che ti piacerebbe essere in grado di verificare l’ordine inverso e normale, ciò sarebbe fatto come:

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

Utenti di Java 8 : usa invece Comparators#isInOrder(Iterable) , poiché il resto Comparators#isInOrder(Iterable) è per lo più obsoleto (come spiegato nella documentazione di class).

Ecco un metodo generico che farà il trucco:

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

Facile:

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

Oppure (se gli elementi sono comparabili):

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

Oppure (se gli elementi non sono comparabili):

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

Le implementazioni non riescono per gli elenchi che contengono valori nulli. Devi aggiungere controlli appropriati in questo caso.

Se si utilizza Java 8, gli stream potrebbero essere in grado di aiutare.

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

Questo codice ordina l’elenco fuori posto e raccoglie i suoi elementi in un altro elenco, che viene quindi confrontato con l’elenco iniziale. Il confronto avrà esito positivo, se entrambe le liste contengono gli stessi elementi in posizioni uguali.

Questo metodo potrebbe non essere la soluzione più rapida, ma è la più semplice da implementare, che non prevede framework di terze parti.

Per verificare se un elenco o qualsiasi struttura di dati per quella materia è un’attività che richiede solo O (n) tempo. Basta scorrere l’elenco usando l’interfaccia Iterator e scorrere i dati (nel tuo caso l’hai già pronto come tipo di Comparabile) dall’inizio alla fine e puoi scoprire se è ordinato o meno

Basta usare l’iteratore per guardare attraverso il contenuto 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; } 

Questo è quello che farei:

 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 non sono sicuro che cosa state facendo, ma questo può essere fatto in un ciclo semplice.

Questa è un’operazione che richiederà O (n) tempo (caso peggiore). Dovrai gestire due casi: dove l’elenco è ordinato in ordine decrescente e dove l’elenco è ordinato in ordine crescente.

Dovrai confrontare ogni elemento con l’elemento successivo assicurandoti che l’ordine sia preservato.

Una semplice implementazione sugli array:

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

Conversione per liste:

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

Se ti serve per il test delle unità, puoi usare AssertJ . Contiene un’asserzione per verificare se un elenco è ordinato:

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

Esiste anche un metodo alternativoSortedAccordingTo che accetta un comparatore nel caso in cui si desideri utilizzare un comparatore personalizzato per l’ordinamento.