Comment fonctionne le tri par insertion ?

Réponse courte

Le tri par insertion maintient un préfixe trié. Il mémorise chaque nouvelle valeur, décale vers la droite les valeurs plus grandes du préfixe, puis place la valeur mémorisée dans l’espace libéré.

Comprendre

Insérer la valeur à sa place

On considère d’abord la première case comme un préfixe trié d’une seule valeur. À chaque étape suivante, on mémorise la valeur à insérer, puis on compare cette valeur aux éléments du préfixe en partant de la droite. Les éléments strictement plus grands sont décalés d’une case vers la droite.

Tracer un exemple

Dans [2, 6, 7, 4, 5], on mémorise 4. On décale 7, puis 6 ; comme 2 n’est pas supérieur à 4, la valeur mémorisée se place après 2. Le tableau devient [2, 4, 6, 7, 5]. Ensuite, 5 prend la place de 6 après avoir décalé 7 et 6 : [2, 4, 5, 6, 7]. Le préfixe rangé gagne une case à chaque insertion.

Préserver les valeurs

La variable qui mémorise la valeur est essentielle : pendant les décalages, une case peut temporairement contenir une copie. Quand la bonne position est trouvée, on écrit la valeur mémorisée à l’indice j + 1. Si le préfixe est déjà trié, une seule comparaison de valeur suffit à chaque nouvelle case ; dans le pire cas, notamment pour un tableau décroissant, le nombre de comparaisons croît comme n².

Deux erreurs à repérer

Écraser la valeur à insérer avant de l’avoir mémorisée fait perdre un élément. Placer cette valeur en t[j] au lieu de t[j + 1] la mettrait avant l’élément qui doit la précéder. Avec des valeurs égales, le test « strictement supérieur » évite de déplacer inutilement une valeur égale.

Étapes

  1. Mémorise la valeur de la prochaine case après le préfixe trié.
  2. Décale d’une case vers la droite chaque valeur du préfixe qui est strictement supérieure à la valeur mémorisée.
  3. Insère la valeur mémorisée dans la case libérée, juste après la dernière valeur qui lui est inférieure ou égale.

Exemples

  • Insérer 4 dans le préfixe [2, 6, 7] décale 7 puis 6 et donne [2, 4, 6, 7].
  • Le passage de [2, 4, 6, 7, 5] à [2, 4, 5, 6, 7] mémorise 5, décale 7 puis 6 et place 5 après 4.
  • Dans [1, 3, 5, 7], insérer 8 ne décale aucune valeur ; le préfixe devient [1, 3, 5, 7, 8].

Pièges fréquents

  • Ne pas sauvegarder la valeur à insérer avant les décalages risque de l’écraser et de perdre une donnée du tableau.
  • Placer la valeur en t[j] au lieu de t[j + 1] la positionne une case trop à gauche après l’arrêt du décalage.

Pourquoi ça marche

Le préfixe était déjà ordonné ; déplacer seulement ses éléments supérieurs à la valeur mémorisée libère exactement l’emplacement où l’insérer sans désordonner les autres.

Et maintenant ?

Questions proches

← Toutes les questions-réponses