Comprendre l'algorithme de tri par insertion (avec des exemples en Java)

Le tri par insertion est un algorithme de tri itératif. Il construit un sous-tableau trié, un élément à la fois, en insérant chaque élément non trié dans sa position correcte dans le sous-tableau trié. Pensez au tri d'une main de cartes à jouer : vous commencez avec une carte triée, puis insérez chaque carte suivante à sa place parmi les cartes déjà triées.

Fonctionnement du tri par insertion

Illustrons avec un exemple de tableau que nous souhaitons trier par ordre croissant :

Première itération :

On considère le premier élément déjà trié. L'algorithme commence par le deuxième élément.

En comparant 2 avec 8, puisque 2 < 8, on décale 8 vers la droite et on insère 2 vers sa gauche.

Deuxième itération :

Nous comparons 6 avec le sous-tableau trié (2, 8). 6 &Lt ; 8, donc 8 décalages vers la droite. Puis, depuis 6 > 2, 6 est placé à droite de 2.

Ce processus se poursuit jusqu'à ce que l'ensemble du tableau soit trié.

Implémentation en Java

<code class="language-java">import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}</code>

Le code itère, en prenant chaque élément comme un key. Il compare ensuite le key avec les éléments de la partie triée, en décalant les éléments plus gros vers la droite jusqu'à ce que la position correcte pour le key soit trouvée.

Par exemple, dans la deuxième itération (i=2) :

Le key vaut 6. La boucle while décale les éléments jusqu'à ce que la position correcte soit trouvée :

Enfin, 6 est inséré :

Sortie :

Tableau non trié : [8, 2, 6, 4, 9, 1] Tableau trié : [1, 2, 4, 6, 8, 9]

Analyse de complexité

• Complexité temporelle :
  • Meilleur cas (O(n)) : tableau déjà trié.
  • Cas moyen (O(n²)) : éléments disposés de manière aléatoire.
  • Pire des cas (O(n²)) : tableau trié inversé.
• Complexité spatiale : O(1) (Algorithme sur place)

Conclusion

La complexité temporelle quadratique du tri par insertion le rend inefficace pour les grands ensembles de données. Cependant, il s'agit d'un algorithme simple qui fonctionne bien sur de petits ensembles de données ou des données presque triées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!