Le tri par insertion fonctionne en séparant conceptuellement le tableau en deux zones : une portion gauche déjà ordonnée et une portion droite non triée. L'algorithme extrait successivement des éléments de la zone non triée et les place à leur position correcte dans la zone triée.

Voici une implémentation initiale qui illustre pas à pas le mécanisme de tri pour un petit tableau :

import java.util.Arrays;

public class TriInsertionDemo {
    public static void main(String[] args) {
        int[] donnees = {8, 3, 7, 1};
        effectuerTriParInsertion(donnees);
    }

    public static void effectuerTriParInsertion(int[] tableau) {
        // Première itération manuelle
        int valeurCourante = tableau[1];
        int positionRecherchee = 0;
        while (positionRecherchee >= 0 && valeurCourante < tableau[positionRecherchee]) {
            tableau[positionRecherchee + 1] = tableau[positionRecherchee];
            positionRecherchee--;
        }
        tableau[positionRecherchee + 1] = valeurCourante;
        System.out.println("État après première insertion :");
        System.out.println(Arrays.toString(tableau));

        // Deuxième itération manuelle
        valeurCourante = tableau[2];
        positionRecherchee = 1;
        while (positionRecherchee >= 0 && valeurCourante < tableau[positionRecherchee]) {
            tableau[positionRecherchee + 1] = tableau[positionRecherchee];
            positionRecherchee--;
        }
        tableau[positionRecherchee + 1] = valeurCourante;
        System.out.println("État après deuxième insertion :");
        System.out.println(Arrays.toString(tableau));

        // Troisième itération manuelle
        valeurCourante = tableau[3];
        positionRecherchee = 2;
        while (positionRecherchee >= 0 && valeurCourante < tableau[positionRecherchee]) {
            tableau[positionRecherchee + 1] = tableau[positionRecherchee];
            positionRecherchee--;
        }
        tableau[positionRecherchee + 1] = valeurCourante;
        System.out.println("État après troisième insertion :");
        System.out.println(Arrays.toString(tableau));
    }
}

La répétition du code ci-dessus suggère une optimisation via une boucle itérative. La version améliorée utilise une boucle for pour parcourir chaque élément et l'insérer dans la partie déjà triée :

import java.util.Arrays;

public class TriInsertionOptimise {
    public static void main(String[] args) {
        int[] ensemble = {42, 15, 89, 4};
        trierParInsertion(ensemble);
    }

    public static void trierParInsertion(int[] arr) {
        for (int pos = 1; pos < arr.length; pos++) {
            int cle = arr[pos];
            int idx = pos - 1;

            while (idx >= 0 && cle < arr[idx]) {
                arr[idx + 1] = arr[idx];
                idx--;
            }
            arr[idx + 1] = cle;
            System.out.println("Après insertion de l'élément à l'index " + pos);
            System.out.println(Arrays.toString(arr));
        }
    }
}

Dans cette version, la variable cle stocke l'élément à insérer, et idx représente l'indice de comparaison dans la zone triée. La boucle while déplace les éléments plus grands vers la droite jusqu'à trouver la position appropriée pour la clé.