Verificare se un elenco è ordinato in Java

1. Panoramica

In questo tutorial, vedremo diversi modi per verificare se un elenco è ordinato in Java .

2. Approccio iterativo

L'approccio iterativo è un modo semplice e intuitivo per verificare la presenza di un elenco ordinato. In questo approccio, itereremo l'elenco e confronteremo gli elementi adiacenti. Se uno qualsiasi dei due elementi adiacenti non è ordinato, possiamo dire che l'elenco non è ordinato.

Un elenco può essere ordinato nell'ordine naturale o in un ordine personalizzato. Copriremo entrambi questi casi utilizzando le interfacce Comparable e Comparator .

2.1. Utilizzo di Comparable

Per prima cosa, vediamo un esempio di un elenco i cui elementi sono di tipo Comparable . Qui, considereremo un elenco contenente oggetti di tipo String :

public static boolean isSorted(List listOfStrings) { if (isEmpty(listOfStrings) || listOfStrings.size() == 1) { return true; } Iterator iter = listOfStrings.iterator(); String current, previous = iter.next(); while (iter.hasNext()) { current = iter.next(); if (previous.compareTo(current) > 0) { return false; } previous = current; } return true; }

2.2. Utilizzo di Comparator

Consideriamo ora una classe Employee , che non implementa Comparable . Quindi, in questo caso, dobbiamo utilizzare un comparatore per confrontare gli elementi adiacenti dell'elenco:

public static boolean isSorted(List employees, Comparator employeeComparator) { if (isEmpty(employees) || employees.size() == 1) { return true; } Iterator iter = employees.iterator(); Employee current, previous = iter.next(); while (iter.hasNext()) { current = iter.next(); if (employeeComparator.compare(previous, current) > 0) { return false; } previous = current; } return true; }

I due esempi precedenti sono simili. L'unica differenza sta nel modo in cui confrontiamo gli elementi precedenti e attuali della lista.

Inoltre, possiamo anche utilizzare Comparator per avere un controllo preciso sul controllo dello smistamento . Ulteriori informazioni su questi due sono disponibili nel nostro tutorial Comparator e Comparable in Java.

3. Approccio ricorsivo

Ora vedremo come verificare la presenza di un elenco ordinato utilizzando la ricorsione:

public static boolean isSorted(List listOfStrings) { return isSorted(listOfStrings, listOfStrings.size()); } public static boolean isSorted(List listOfStrings, int index) { if (index  0) { return false; } else { return isSorted(listOfStrings, index - 1); } }

4. Utilizzando Guava

Spesso è utile utilizzare una libreria di terze parti invece di scrivere la nostra logica. La libreria Guava ha alcune classi di utilità che possiamo usare per controllare se un elenco è ordinato.

4.1. Classe di ordinazione Guava

In questa sezione vedremo come utilizzare la classe Ordering in Guava per verificare la presenza di un elenco ordinato.

Per prima cosa, vedremo un esempio di un elenco contenente elementi di tipo Comparable :

public static boolean isSorted(List listOfStrings) { return Ordering. natural().isOrdered(listOfStrings); }

Successivamente, vedremo come possiamo verificare se un elenco di oggetti Employee è ordinato utilizzando un Comparatore :

public static boolean isSorted(List employees, Comparator employeeComparator) { return Ordering.from(employeeComparator).isOrdered(employees); }

Inoltre, possiamo usare natural (). ReverseOrder () per controllare se un elenco è ordinato in ordine inverso. Inoltre, possiamo usare natural (). NullFirst () e natural () . nullLast () per verificare se null appare al primo o all'ultimo dell'elenco ordinato.

Per saperne di più sulla classe di ordinazione di Guava , possiamo fare riferimento alla nostra guida all'articolo sull'ordinazione di Guava.

4.2. Classe di comparatori di guava

Se stiamo usando Java 8 o superiore, Guava fornisce un'alternativa migliore in termini di classe Comparatori . Vedremo un esempio di utilizzo del metodo isInOrder di questa classe:

public static boolean isSorted(List listOfStrings) { return Comparators.isInOrder(listOfStrings, Comparator. naturalOrder()); }

Come possiamo vedere, nell'esempio precedente, abbiamo utilizzato l'ordine naturale per verificare la presenza di un elenco ordinato. Possiamo anche utilizzare un comparatore per personalizzare il controllo di ordinamento.

5. conclusione

In questo articolo, abbiamo visto come possiamo verificare la presenza di un elenco ordinato utilizzando un semplice approccio iterativo, un approccio ricorsivo e utilizzando Guava. Abbiamo anche accennato brevemente all'uso di Comparator e Comparable nel decidere la logica di controllo dell'ordinamento.

L'implementazione di tutti questi esempi e frammenti di codice può essere trovata su GitHub.