Tri par sélection en Java : exemple pas à pas et code complet

Qu'est-ce que le tri par sélection ?

Le tri par sélection est un algorithme simple basé sur les comparaisons qui sélectionne répétitivement le plus petit élément restant et l'échange en place. Bien que pas le plus rapide pour de grands ensembles de données, sa simplicité le rend idéal pour l'éducation et les petits tableaux.

Comment fonctionne l'algorithme

• Commencer au début du tableau.
• Trouver le plus petit élément dans la partie non triée.
• L'échanger avec l'élément à la position courante.
• Déplacer la frontière entre parties triée et non triée d'un pas vers la droite.
• Répéter jusqu'à ce que tout le tableau soit trié.

Implémentation Java

Voici un programme Java concis qui démontre l'algorithme de tri par sélection sur un tableau d'entiers. Le code affiche le tableau avant et après le tri, ainsi que les étapes intermédiaires pour illustrer chaque passe.

package com.guru99;
public class TriSelectionAlgo {
    public static void main(String[] args) {
        int[] monTableau = {860, 8, 200, 9};
        System.out.println("------Avant tri par sélection-----");
        afficherTableau(monTableau);
        selection(monTableau); // Trier le tableau
        System.out.println("-----Après tri par sélection-----");
        afficherTableau(monTableau);
    }
    public static void selection(int[] tableau) {
        for (int i = 0; i < tableau.length - 1; i++) {
            System.out.println("Passe de tri numéro " + (i + 1));
            int index = i;
            for (int j = i + 1; j < tableau.length; j++) {
                System.out.println("Comparaison " + tableau[index] + " et " + tableau[j]);
                if (tableau[j] < tableau[index]) {
                    System.out.println(tableau[index] + " est plus grand que " + tableau[j]);
                    index = j;
                }
            }
            int plusPetitNombre = tableau[index];
            tableau[index] = tableau[i];
            tableau[i] = plusPetitNombre;
            System.out.println("Échange des éléments : Nouveau tableau après échange");
            afficherTableau(tableau);
        }
    }
    private static void afficherTableau(int[] tableau) {
        for (int i = 0; i < tableau.length; i++) {
            System.out.print(tableau[i] + " ");
        }
        System.out.println();
    }
}

Exemple de sortie

------Avant tri par sélection-----
860 8 200 9
Passe de tri numéro 1
Comparaison 860 et 8
860 est plus grand que 8
Comparaison 8 et 200
Comparaison 8 et 9
Échange des éléments : Nouveau tableau après échange
8 860 200 9
Passe de tri numéro 2
Comparaison 860 et 200
860 est plus grand que 200
Comparaison 200 et 9
200 est plus grand que 9
Échange des éléments : Nouveau tableau après échange
8 9 200 860
Passe de tri numéro 3
Comparaison 200 et 860
Échange des éléments : Nouveau tableau après échange
8 9 200 860
-----Après tri par sélection-----
8 9 200 860

Notes de performance

Le tri par sélection effectue O(n²) comparaisons quel que soit l'entrée et utilise au maximum O(1) mémoire additionnelle. Son comportement déterministe le rend adapté aux environnements où la mémoire est contrainte.