Maîtriser les algorithmes de collection Java : Tri, mélange et plus

Maîtriser les algorithmes de collection Java : Tri, mélange et plus

Le framework Java Collections fournit un ensemble riche de méthodes statiques — souvent appelées algorithmes génériques — qui permettent de manipuler des structures de données sans écrire de code répétitif. Ces utilitaires fonctionnent avec toute collection implémentant l'interface Collection, offrant simplicité et performance.

---

1. Tri avec Collections.sort()

La méthode sort() ordonne les éléments dans l'ordre naturel (croissant). Pour un ordre personnalisé, fournissez un Comparator.

import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nombres = new ArrayList<>();
        nombres.add(4);
        nombres.add(2);
        nombres.add(3);
        System.out.println("ArrayList non trié : " + nombres);
        Collections.sort(nombres);
        System.out.println("ArrayList trié : " + nombres);
    }
}

Sortie

ArrayList non trié : [4, 2, 3]
ArrayList trié : [2, 3, 4]

Pour un ordre décroissant ou des critères spécifiques, utilisez un Comparator personnalisé.

---

2. Mélange aléatoire avec Collections.shuffle()

Utilisez shuffle() pour randomiser la séquence des éléments, idéal pour les jeux ou l'échantillonnage.

import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nombres = new ArrayList<>();
        nombres.add(1);
        nombres.add(2);
        nombres.add(3);
        System.out.println("ArrayList trié : " + nombres);
        Collections.shuffle(nombres);
        System.out.println("ArrayList après mélange : " + nombres);
    }
}

Sortie

ArrayList trié : [1, 2, 3]
ArrayList après mélange : [2, 1, 3]

Chaque exécution produit une permutation différente grâce à l'algorithme Fisher-Yates sous-jacent.

---

3. Manipulation courante des données

Java offre une suite de méthodes utilitaires pour transformer les collections :

• reverse() – inverse l'ordre des éléments
• fill() – remplace chaque élément par une valeur spécifiée
• copy() – copie les éléments d'une collection vers une autre (de même taille)
• swap() – échange deux éléments par index
• addAll() – ajoute tous les éléments d'une collection à une autre

import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nombres = new ArrayList<>();
        nombres.add(1);
        nombres.add(2);
        System.out.println("ArrayList1 : " + nombres);

        Collections.reverse(nombres);
        System.out.println("ArrayList1 inversé : " + nombres);

        Collections.swap(nombres, 0, 1);
        System.out.println("ArrayList1 après swap() : " + nombres);

        ArrayList<Integer> nouveauxNombres = new ArrayList<>();
        nouveauxNombres.addAll(nombres);
        System.out.println("ArrayList2 avec addAll() : " + nouveauxNombres);

        Collections.fill(nombres, 0);
        System.out.println("ArrayList1 après fill() : " + nombres);

        Collections.copy(nouveauxNombres, nombres);
        System.out.println("ArrayList2 après copy() : " + nouveauxNombres);
    }
}

Sortie

ArrayList1 : [1, 2]
ArrayList1 inversé : [2, 1]
ArrayList1 après swap() : [1, 2]
ArrayList2 avec addAll() : [1, 2]
ArrayList1 après fill() : [0, 0]
ArrayList2 après copy() : [0, 0]

Note : copy() nécessite que la collection de destination ait au moins autant d'éléments que la source.

---

4. Recherche binaire avec Collections.binarySearch()

Localisez efficacement un élément dans une collection triée. La méthode renvoie l'index de l'élément ou un point d'insertion négatif s'il n'est pas trouvé.

import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nombres = new ArrayList<>();
        nombres.add(1);
        nombres.add(2);
        nombres.add(3);
        int pos = Collections.binarySearch(nombres, 3);
        System.out.println("La position de 3 est " + pos);
    }
}

Sortie

La position de 3 est 2.

Astuce : Triez toujours la collection avant d'appeler binarySearch() ; sinon le résultat est indéfini.

---

5. Composition de collections

Ces utilitaires analysent les relations entre collections :

• frequency() – compte les occurrences d'un élément spécifique
• disjoint() – vérifie si deux collections n'ont aucun élément commun

import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nombres = new ArrayList<>();
        nombres.add(1);
        nombres.add(2);
        nombres.add(3);
        nombres.add(2);
        System.out.println("ArrayList1 : " + nombres);

        int compte = Collections.frequency(nombres, 2);
        System.out.println("Nombre de 2 : " + compte);

        ArrayList<Integer> nouveauxNombres = new ArrayList<>();
        nouveauxNombres.add(5);
        nouveauxNombres.add(6);
        System.out.println("ArrayList2 : " + nouveauxNombres);

        boolean disjoint = Collections.disjoint(nombres, nouveauxNombres);
        System.out.println("Les deux listes sont disjointes : " + disjoint);
    }
}

Sortie

ArrayList1 : [1, 2, 3, 2]
Nombre de 2 : 2
ArrayList2 : [5, 6]
Les deux listes sont disjointes : true

---

6. Trouver le minimum et le maximum

Récupérez le plus petit ou le plus grand élément avec min() et max() — utiles pour l'analyse et les vérifications de bornes.

import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nombres = new ArrayList<>();
        nombres.add(1);
        nombres.add(2);
        nombres.add(3);
        int min = Collections.min(nombres);
        System.out.println("Élément minimum : " + min);
        int max = Collections.max(nombres);
        System.out.println("Élément maximum : " + max);
    }
}

Sortie

Élément minimum : 1
Élément maximum : 3