Comment vérifier si une liste est triée en Java

Introduction

Dans ce laboratoire (lab), vous apprendrez à vérifier si une liste est triée en Java. Nous explorerons différentes approches pour accomplir cette tâche, en commençant par une méthode de base consistant à comparer les éléments adjacents de la liste.

Vous découvrirez ensuite comment tirer parti de la puissance de l'API Stream de Java pour effectuer la vérification de tri de manière plus concise et potentiellement plus efficace. Enfin, nous aborderons la question de la gestion des différents ordres de tri, tels que l'ordre croissant et décroissant, pour rendre vos vérifications de tri plus polyvalentes.

Comparer les éléments adjacents d'une liste

Dans cette étape, nous apprendrons à comparer les éléments adjacents d'une liste (plus précisément, d'une List en Java). C'est une tâche courante lorsque vous devez vérifier des motifs ou un ordre dans une séquence de données. Nous commencerons par créer un simple programme Java qui utilise une boucle pour parcourir une liste et comparer chaque élément avec celui qui le suit immédiatement.

Tout d'abord, créons un nouveau fichier Java nommé ListComparison.java dans votre répertoire ~/project. Vous pouvez le faire en utilisant l'explorateur de fichiers de l'IDE Web à gauche. Cliquez avec le bouton droit dans la zone ~/project, sélectionnez "Nouveau fichier" et tapez ListComparison.java.

Maintenant, ouvrez le fichier ListComparison.java dans l'éditeur et ajoutez le code suivant :

import java.util.ArrayList;
import java.util.List;

public class ListComparison {

    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(3);
        numbers.add(2);
        numbers.add(4);
        numbers.add(5);

        System.out.println("Original list: " + numbers);

        // Loop through the list, comparing adjacent elements
        for (int i = 0; i < numbers.size() - 1; i++) {
            Integer currentElement = numbers.get(i);
            Integer nextElement = numbers.get(i + 1);

            System.out.println("Comparing " + currentElement + " and " + nextElement);

            if (currentElement < nextElement) {
                System.out.println(currentElement + " is less than " + nextElement);
            } else if (currentElement > nextElement) {
                System.out.println(currentElement + " is greater than " + nextElement);
            } else {
                System.out.println(currentElement + " is equal to " + nextElement);
            }
        }
    }
}

Décortiquons ce code :

• import java.util.ArrayList; et import java.util.List; : Ces lignes importent les classes nécessaires pour travailler avec des listes en Java.
• List<Integer> numbers = new ArrayList<>(); : Cela crée une nouvelle liste appelée numbers qui peut contenir des objets Integer (nombres entiers).
• numbers.add(...) : Ces lignes ajoutent des éléments à notre liste.
• for (int i = 0; i < numbers.size() - 1; i++) : Il s'agit d'une boucle for qui parcourt la liste. Notez que la condition de boucle est i < numbers.size() - 1. Cela est important car nous comparons numbers.get(i) avec numbers.get(i + 1). Si nous parcourions jusqu'à numbers.size(), i + 1 dépasserait les limites lors de la dernière itération.
• Integer currentElement = numbers.get(i); : Cela récupère l'élément à l'index actuel i.
• Integer nextElement = numbers.get(i + 1); : Cela récupère l'élément à l'index suivant i + 1.
• System.out.println(...) : Ces lignes affichent des informations dans la console, montrant quels éléments sont comparés et le résultat de la comparaison.
• if, else if, else : Ce sont des instructions conditionnelles qui vérifient si l'currentElement est inférieur, supérieur ou égal à l'nextElement.

Enregistrez le fichier ListComparison.java (Ctrl+S ou Cmd+S).

Maintenant, compilons et exécutons le programme. Ouvrez le terminal en bas de l'IDE Web. Assurez-vous d'être dans le répertoire ~/project (vous pouvez utiliser cd ~/project si nécessaire).

Compilez le code en utilisant javac :

javac ListComparison.java

S'il n'y a pas d'erreurs, un fichier ListComparison.class sera créé. Maintenant, exécutez le code compilé en utilisant java :

java ListComparison

Vous devriez voir une sortie similaire à celle-ci :

Original list: [1, 3, 2, 4, 5]
Comparing 1 and 3
1 is less than 3
Comparing 3 and 2
3 is greater than 2
Comparing 2 and 4
2 is less than 4
Comparing 4 and 5
4 is less than 5

Cette sortie montre que notre programme a réussi à parcourir la liste et à comparer chaque paire d'éléments adjacents, affichant le résultat de chaque comparaison.

Utiliser l'API Stream pour vérifier le tri

Dans cette étape, nous explorerons une méthode plus moderne et souvent plus concise pour vérifier si une liste est triée en utilisant l'API Stream de Java. L'API Stream, introduite en Java 8, offre une approche fonctionnelle pour traiter des collections de données.

Nous allons modifier notre programme précédent pour inclure une méthode qui vérifie si la liste est triée par ordre croissant en utilisant les flux (streams).

Ouvrez le fichier ListComparison.java dans l'éditeur de l'IDE Web. Ajoutez une nouvelle méthode appelée isSortedAscending à la classe ListComparison, en dehors de la méthode main mais à l'intérieur des accolades {} de la classe ListComparison.

Voici le code mis à jour pour ListComparison.java :

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class ListComparison {

    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(3);
        numbers.add(2);
        numbers.add(4);
        numbers.add(5);

        System.out.println("Original list: " + numbers);

        // Check if the list is sorted using the new method
        boolean sorted = isSortedAscending(numbers);

        if (sorted) {
            System.out.println("The list is sorted in ascending order.");
        } else {
            System.out.println("The list is NOT sorted in ascending order.");
        }

        // The previous loop for comparison is removed for simplicity in this step
        // but you can keep it if you want to see both methods in action.
    }

    // Method to check if the list is sorted in ascending order using Streams
    public static boolean isSortedAscending(List<Integer> list) {
        if (list == null || list.size() <= 1) {
            return true; // An empty or single-element list is considered sorted
        }

        return IntStream.range(0, list.size() - 1)
                .allMatch(i -> list.get(i).compareTo(list.get(i + 1)) <= 0);
    }
}

Examinons les nouvelles parties :

• import java.util.stream.IntStream; : Cela importe la classe IntStream, qui est utile pour travailler avec des séquences d'entiers dans les flux.
• public static boolean isSortedAscending(List<Integer> list) : Cela déclare une nouvelle méthode statique nommée isSortedAscending qui prend une List d'Integer et renvoie un boolean (true si triée, false sinon).
• if (list == null || list.size() <= 1) : Cela gère les cas limites : une liste vide ou une liste avec un seul élément est toujours considérée comme triée.
• IntStream.range(0, list.size() - 1) : Cela crée un flux d'entiers de 0 jusqu'à (mais sans inclure) list.size() - 1. Ces entiers représentent les indices des éléments de la liste que nous voulons comparer.
• .allMatch(i -> list.get(i).compareTo(list.get(i + 1)) <= 0) : C'est le cœur de l'opération de flux.
  • allMatch() est une opération terminale qui vérifie si tous les éléments du flux correspondent à une condition donnée.
  • i -> list.get(i).compareTo(list.get(i + 1)) <= 0 est une expression lambda qui définit la condition. Pour chaque index i du IntStream, elle récupère l'élément à l'index i et l'élément à l'index i + 1.
  • list.get(i).compareTo(list.get(i + 1)) compare les deux éléments. compareTo renvoie un entier négatif si le premier élément est inférieur au deuxième, zéro s'ils sont égaux et un entier positif si le premier élément est supérieur au deuxième.
  • <= 0 vérifie si le résultat de compareTo est inférieur ou égal à zéro. Cette condition est vraie si l'élément actuel est inférieur ou égal à l'élément suivant, ce qui est la définition de l'ordre croissant.
  • allMatch renvoie true seulement si cette condition est vraie pour toutes les paires adjacentes de la liste.

Enregistrez le fichier ListComparison.java.

Maintenant, compilez et exécutez le programme mis à jour dans le terminal :

javac ListComparison.java

java ListComparison

La sortie devrait maintenant indiquer si la liste est triée par ordre croissant en fonction de la méthode isSortedAscending :

Original list: [1, 3, 2, 4, 5]
The list is NOT sorted in ascending order.

Modifiez la liste dans la méthode main pour qu'elle soit triée, par exemple :

        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);
        numbers.add(4);
        numbers.add(5);

Enregistrez le fichier, compilez et exécutez à nouveau. La sortie devrait maintenant être :

Original list: [1, 2, 3, 4, 5]
The list is sorted in ascending order.

Cela démontre comment utiliser l'API Stream pour effectuer une vérification concise de l'ordre croissant.

Gérer différents ordres de tri

Dans l'étape précédente, nous avons créé une méthode pour vérifier si une liste est triée par ordre croissant. Dans cette étape, nous allons étendre notre programme pour gérer différents ordres de tri : croissant et décroissant. Nous allons ajouter une nouvelle méthode qui prend la liste et l'ordre de tri souhaité en entrée.

Ouvrez le fichier ListComparison.java dans l'éditeur de l'IDE Web. Nous allons ajouter une nouvelle méthode appelée isSorted qui prend la liste et un boolean indiquant si nous voulons vérifier l'ordre croissant (true) ou décroissant (false).

Voici le code mis à jour pour ListComparison.java :

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class ListComparison {

    public static void main(String[] args) {
        List<Integer> numbersAsc = new ArrayList<>();
        numbersAsc.add(1);
        numbersAsc.add(2);
        numbersAsc.add(3);
        numbersAsc.add(4);
        numbersAsc.add(5);

        List<Integer> numbersDesc = new ArrayList<>();
        numbersDesc.add(5);
        numbersDesc.add(4);
        numbersDesc.add(3);
        numbersDesc.add(2);
        numbersDesc.add(1);

        List<Integer> numbersUnsorted = new ArrayList<>();
        numbersUnsorted.add(1);
        numbersUnsorted.add(3);
        numbersUnsorted.add(2);
        numbersUnsorted.add(4);
        numbersUnsorted.add(5);


        System.out.println("Checking list: " + numbersAsc);
        System.out.println("Is ascending sorted? " + isSorted(numbersAsc, true));
        System.out.println("Is descending sorted? " + isSorted(numbersAsc, false));
        System.out.println();

        System.out.println("Checking list: " + numbersDesc);
        System.out.println("Is ascending sorted? " + isSorted(numbersDesc, true));
        System.out.println("Is descending sorted? " + isSorted(numbersDesc, false));
        System.out.println();

        System.out.println("Checking list: " + numbersUnsorted);
        System.out.println("Is ascending sorted? " + isSorted(numbersUnsorted, true));
        System.out.println("Is descending sorted? " + isSorted(numbersUnsorted, false));
        System.out.println();

    }

    // Method to check if the list is sorted based on the specified order
    public static boolean isSorted(List<Integer> list, boolean ascending) {
        if (list == null || list.size() <= 1) {
            return true; // An empty or single-element list is considered sorted
        }

        return IntStream.range(0, list.size() - 1)
                .allMatch(i -> {
                    int comparison = list.get(i).compareTo(list.get(i + 1));
                    if (ascending) {
                        return comparison <= 0; // For ascending, current must be <= next
                    } else {
                        return comparison >= 0; // For descending, current must be >= next
                    }
                });
    }
}

Examinons les modifications :

• Nous avons créé trois listes différentes dans main : numbersAsc (triée par ordre croissant), numbersDesc (triée par ordre décroissant) et numbersUnsorted.
• Nous appelons la nouvelle méthode isSorted avec chaque liste et avec true (pour l'ordre croissant) et false (pour l'ordre décroissant) pour le paramètre ascending.
• public static boolean isSorted(List<Integer> list, boolean ascending) : C'est la nouvelle signature de notre méthode, qui accepte la liste et un indicateur booléen pour l'ordre.
• À l'intérieur de la lambda allMatch :
  • int comparison = list.get(i).compareTo(list.get(i + 1)); : Nous effectuons la comparaison entre les éléments adjacents.
  • if (ascending) : Si le drapeau ascending est vrai, nous vérifions si comparison <= 0 (l'élément actuel est inférieur ou égal à l'élément suivant).
  • else : Si le drapeau ascending est faux (ce qui signifie que nous vérifions l'ordre décroissant), nous vérifions si comparison >= 0 (l'élément actuel est supérieur ou égal à l'élément suivant).

Enregistrez le fichier ListComparison.java.

Maintenant, compilez et exécutez le programme mis à jour dans le terminal :

javac ListComparison.java

java ListComparison

La sortie devrait montrer les résultats de la vérification de chaque liste par rapport aux ordres croissant et décroissant :

Checking list: [1, 2, 3, 4, 5]
Is ascending sorted? true
Is descending sorted? false

Checking list: [5, 4, 3, 2, 1]
Is ascending sorted? false
Is descending sorted? true

Checking list: [1, 3, 2, 4, 5]
Is ascending sorted? false
Is descending sorted? false

Cela démontre comment créer une méthode flexible en utilisant l'API Stream pour vérifier différents ordres de tri en ajustant la logique de comparaison en fonction d'un paramètre d'entrée.

Résumé

Dans ce laboratoire (lab), nous avons appris à vérifier si une liste est triée en Java en utilisant différentes approches. Nous avons commencé par implémenter une méthode pour comparer les éléments adjacents d'une liste en utilisant une boucle traditionnelle, ce qui offre une compréhension fondamentale de la logique de vérification du tri. Cela consistait à parcourir la liste et à comparer chaque élément avec son successeur pour identifier les paires non triées.

Ensuite, nous avons exploré comment tirer parti de l'API Stream de Java pour une approche plus concise et fonctionnelle de la vérification de l'ordre d'une liste. Cette méthode utilise des opérations de flux pour déterminer efficacement si les éléments sont dans l'ordre souhaité. Enfin, nous avons abordé la gestion de différents ordres de tri (croissant et décroissant) lors de la vérification du tri, démontrant comment adapter la logique de comparaison pour répondre à diverses exigences de tri.