Vérifier si une liste est triée en Java

1. Vue d'ensemble

Dans ce didacticiel, nous verrons différentes façons de vérifier si une liste est triée en Java .

2. Approche itérative

L'approche itérative est un moyen simple et intuitif de rechercher une liste triée. Dans cette approche, nous allons itérer la liste et comparer les éléments adjacents. Si l'un des deux éléments adjacents n'est pas trié, nous pouvons dire que la liste n'est pas triée.

Une liste peut être triée dans l'ordre naturel ou dans un ordre personnalisé. Nous couvrirons ces deux cas en utilisant les interfaces Comparable et Comparator .

2.1. Utilisation de comparable

Voyons d'abord un exemple de liste dont les éléments sont de type Comparable . Ici, nous allons considérer une liste contenant des objets de type 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. Utilisation du comparateur

Maintenant, considérons une classe Employee , qui n'implémente pas Comparable . Donc, dans ce cas, nous devons utiliser un comparateur pour comparer les éléments adjacents de la liste:

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

Les deux exemples ci-dessus sont similaires. La seule différence réside dans la façon dont nous comparons les éléments précédents et actuels de la liste.

De plus, nous pouvons également utiliser Comparator pour avoir un contrôle précis sur le contrôle de tri . De plus amples informations sur ces deux éléments sont disponibles dans notre tutoriel Comparateur et Comparable en Java.

3. Approche récursive

Maintenant, nous allons voir comment vérifier une liste triée en utilisant la récursivité:

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. Utilisation de la goyave

Il est souvent bon d'utiliser une bibliothèque tierce au lieu d'écrire notre propre logique. La bibliothèque Guava a quelques classes utilitaires que nous pouvons utiliser pour vérifier si une liste est triée.

4.1. Classe de commande de goyave

Dans cette section, nous verrons comment utiliser la classe Ordering dans Guava pour rechercher une liste triée.

Tout d'abord, nous allons voir un exemple de liste contenant des éléments de type Comparable :

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

Ensuite, nous verrons comment nous pouvons vérifier si une liste d' objets Employé est triée à l'aide d'un comparateur :

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

De plus, nous pouvons utiliser natural (). ReverseOrder () pour vérifier si une liste est triée dans l'ordre inverse. De plus, nous pouvons utiliser natural (). NullFirst () et natural () . nullLast () pour vérifier si null apparaît au premier ou au dernier de la liste triée.

Pour en savoir plus sur la classe de commande de goyave , nous pouvons consulter notre article Guide de commande de goyave.

4.2. Classe de comparateurs de goyave

Si nous utilisons Java 8 ou supérieur, Guava offre une meilleure alternative en termes de classe Comparators . Nous verrons un exemple d' utilisation de la méthode isInOrder de cette classe:

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

Comme nous pouvons le voir, dans l'exemple ci-dessus, nous avons utilisé l'ordre naturel pour vérifier une liste triée. Nous pouvons également utiliser un comparateur pour personnaliser le contrôle de tri.

5. Conclusion

Dans cet article, nous avons vu comment nous pouvons rechercher une liste triée en utilisant une approche itérative simple, une approche récursive et en utilisant Guava. Nous avons également brièvement évoqué l'utilisation de Comparator et de Comparable pour décider de la logique de contrôle de tri.

L'implémentation de tous ces exemples et extraits de code peut être trouvée sur GitHub.