Algorithme de tri par insertion en Java : exemple clair et guide pas à pas

Qu'est-ce que l'algorithme de tri par insertion ?

Le tri par insertion est une technique de tri simple, idéale pour les petits ensembles de données ou presque triés. À chaque itération, l'algorithme retire un élément, le compare aux éléments précédents, et le place à sa position correcte.

Le tri par insertion fonctionne en O(n²) dans le pire et le cas moyen, mais atteint une performance linéaire quand le tableau est déjà trié. C'est un tri sur place, stable, qui ne nécessite qu'un espace supplémentaire constant.

Processus du tri par insertion

Voici une représentation visuelle du flux de travail du tri par insertion :

Processus de l'algorithme de tri par insertion

Programme Java pour trier un tableau avec le tri par insertion :

package com.guru99;
public class ExempleTriInsertion {
    public static void main(String a[]) {
        int[] monTableau = {860,8,200,9};
        System.out.println("Avant tri par insertion");
        afficherTableau(monTableau);
        triInsertion(monTableau); // tri du tableau par insertion
        System.out.println("Après tri par insertion");
        afficherTableau(monTableau);
    }
    public static void triInsertion(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            System.out.println("Passe de tri numéro " + (i));
            int cle = arr[i];
            int j = i-1;
            while ( (j > -1) && ( arr[j] > cle ) ) {
                System.out.println("Comparaison " + cle + " et " + arr[j]);
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = cle;
            System.out.println("Échange des éléments : Nouveau tableau après échange");
            afficherTableau(arr);
        }
    }
    static void afficherTableau(int[] tableau){
        for(int i=0; i < tableau.length; i++) {
            System.out.print(tableau[i] + " ");
        }
        System.out.println();
    }
}

Sortie du code :

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