Le tri par insertion

Agrandir une partie déjà triée

La première valeur forme à elle seule une partie triée. Au passage i = 1, on insère la deuxième dans cette partie. Au passage suivant, on insère la troisième dans les deux précédentes, et ainsi de suite. Pour [5, 2, 4, 1], les états successifs sont [2, 5, 4, 1], [2, 4, 5, 1] puis [1, 2, 4, 5].

Contrairement à la sélection, le préfixe trié ne contient pas nécessairement les plus petites valeurs du tableau entier. Après le premier passage, 1 reste à droite. Le préfixe rassemble les valeurs initialement rencontrées, mais dans le bon ordre.

Sauvegarder avant de décaler

La valeur à insérer doit être conservée dans une variable avant tout déplacement. On compare ensuite les éléments du préfixe en remontant depuis sa fin. Tant qu’ils sont strictement plus grands, on les décale d’une case vers la droite. Quand on atteint une valeur plus petite ou égale, ou le début du tableau, on place la valeur sauvegardée dans l’espace disponible.

Il faut tester que l’indice reste valide avant de lire la case. En Python, les indices négatifs désignent des cases depuis la fin ; ils ne signalent pas automatiquement l’erreur logique qu’un dépassement à gauche pourrait provoquer.

def tri_insertion(t):
    for i in range(1, len(t)):
        valeur = t[i]
        j = i - 1
        while j >= 0 and t[j] > valeur:
            t[j + 1] = t[j]
            j = j - 1
        t[j + 1] = valeur

Pendant les décalages, le tableau peut provisoirement contenir deux copies d’une même valeur. Ce n’est pas une perte de donnée si la valeur à insérer est conservée ailleurs. L’ensemble « tableau plus variable sauvegardée plus emplacement libre » représente l’état réel du raisonnement. Regardez donc aussi les variables temporaires, et pas seulement la photographie intermédiaire du tableau.

Construire la preuve avec le préfixe

Au début du passage i, les i premières cases sont triées et contiennent les valeurs initiales de ce préfixe. Les décalages laissent entre elles les valeurs supérieures dans le même ordre. L’insertion place la valeur courante après les valeurs inférieures ou égales et avant les valeurs supérieures. Le préfixe de longueur i + 1 est donc trié.

La sauvegarde permet de conserver chaque valeur malgré les copies temporaires. Pour la terminaison de la boucle interne, l’indice j diminue à chaque décalage et ne peut pas rester indéfiniment positif. La boucle externe est bornée par la taille du tableau.

L’ordre initial change le travail

Dans un tableau déjà trié, chaque nouvelle valeur est immédiatement à la bonne place : une comparaison de valeurs suffit par passage et aucun décalage n’est nécessaire. Dans un tableau strictement décroissant, chaque valeur doit passer devant toutes les précédentes. Il y a alors 1 + 2 + … + (n - 1) décalages, soit n(n - 1) / 2.

Le pire coût est quadratique, mais le meilleur cas est linéaire pour cette version. L’atelier compte les comparaisons entre valeurs et les décalages séparément ; les tests d’indice ne figurent pas dans ce compteur. Cette convention doit rester identique lorsque l’on compare deux exemples.

Pour [2,5,8,4], la dernière insertion compare 8 à 4, puis 5 à 4, puis 2 à 4. Deux comparaisons déclenchent un décalage ; la troisième arrête la remontée. Le nombre de comparaisons peut donc dépasser celui des décalages. En revanche, quand la remontée atteint le bord gauche, l’arrêt peut être déterminé par l’indice sans dernière comparaison entre valeurs.

Exemple suivi : ouvrir une place sans perdre la clé

Insérons 3 dans le préfixe [1,4,6], suivi de 3. On sauvegarde d’abord valeur=3. Copier 6 vers la droite donne provisoirement [1,4,6,6]. Copier 4 donne [1,4,4,6]. La comparaison avec 1 arrête la boucle ; écrire la sauvegarde dans la case libre produit [1,3,4,6].

Le chemin des indices est aussi important : on commence à 2, on passe à 1 puis à 0, et on insère à j+1=1. L’algorithme ne perd pas 3 puisque la variable le conserve. Pour une valeur plus petite que toutes les précédentes, les indices vont jusqu’à -1 puis l’insertion se fait à 0. Le test de validité doit précéder l’accès à la case, en particulier dans Python où un indice négatif peut donner une valeur valide mais indésirable.

Doublons, stabilité et jeu de tests

Approfondissement : avec un décalage uniquement lorsque la clé précédente est strictement supérieure, les clés égales gardent leur ordre relatif. Sur [(2,A),(2,B),(1,C)], A ne se déplace pas devant B lors de l’insertion de B. L’insertion de C décale ensuite B puis A, mais leur ordre relatif final reste A puis B. On appelle stable un tri possédant cette propriété.

Pour vérifier la version numérique, prenez un tableau vide, un singleton, une suite croissante, une suite décroissante et des répétitions. Le vide et le singleton ne nécessitent aucune insertion. La suite croissante vérifie l’arrêt immédiat des boucles internes ; la décroissante force le passage jusqu’au bord gauche. Les répétitions vérifient que le test strict ne décale pas inutilement les égaux. Un unique tableau mélangé ne met pas nécessairement en évidence toutes ces branches.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Placer la sauvegarde en t[j] au lieu de t[j + 1].

La boucle s’arrête sur la case précédente ou j = -1. L’emplacement libre se trouve une case plus loin.

Oublier la conservation des valeurs dans la preuve.

Des copies temporaires existent pendant les décalages. La variable sauvegardée permet de reconstituer le préfixe sans perte.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2026 · Amérique du Nord · Jour 2 : Tennis : objets, tri et arbre du tournoi
• Bac 2025 · Centres étrangers groupe 1 · Jour 2 : Dictionnaire de mots : hachage, insertion ordonnée et dichotomie
• Bac 2025 · Amérique du Nord · Jour 2 bis - Sujet PE2 : Construire et utiliser un arbre de compression de Huffman

Le prochain pas

• Le tri par sélection
• Prouver la correction et la terminaison d’un algorithme
• Le tri fusion

Retrouver le catalogue de Première

Ce chapitre s’appuie sur le programme officiel de Première (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.