Numérique et sciences informatiques (spécialité) · Première

Tris par insertion et par sélection : cours de Première NSI

Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur

L'essentiel

Un tri range les éléments d'une liste dans l'ordre croissant ; le tri par sélection et le tri par insertion le font avec deux boucles imbriquées.
Sélection : à chaque tour, on cherche le minimum de la partie non triée et on l'échange avec le premier élément de cette partie.
Insertion : à chaque tour, on prend l'élément suivant et on le glisse à sa place dans la partie gauche, déjà triée.
La correction se prouve par un invariant de boucle : au début du tour $i$ , les cases t[0:i] sont triées.
Le coût est quadratique dans le pire cas : le tri par sélection fait toujours $\frac{n(n-1)}{2}$ comparaisons, le tri par insertion peut faire beaucoup moins sur une liste presque triée.

Pourquoi trier une liste ?

Trier consiste à ranger des éléments selon un ordre : des nombres du plus petit au plus grand, des mots dans l'ordre alphabétique, des élèves selon leur moyenne. Une fois les données rangées, beaucoup de traitements deviennent plus simples. Chercher une valeur, trouver la médiane ou repérer les doublons demande moins d'efforts sur une liste ordonnée que sur une liste en désordre. Tu verras d'ailleurs bientôt la recherche dichotomique, qui exige une liste déjà triée.

Dans ce cours, tu étudies deux algorithmes de tri classiques de la classe de Première : le tri par sélection et le tri par insertion. Le programme de NSI te demande de les connaître, de les dérouler sur un exemple, de les écrire en Python, de justifier leur correction grâce à un invariant de boucle et d'estimer leur coût.¹⁵

Tu pars de ce que tu maîtrises déjà : le parcours séquentiel d'un tableau, avec une boucle for qui visite les cases une à une. Les deux tris reposent sur ce parcours, répété plusieurs fois.

Ce qu'est un algorithme de tri

Les deux tris que tu étudies ont la même idée générale : la liste est coupée en deux zones.

une zone triée, à gauche, qui grandit à chaque tour ;
une zone non triée, à droite, qui rétrécit à chaque tour.

Au départ, la zone triée est vide (ou réduite à une case pour l'insertion) et la zone non triée occupe tout le reste de la liste. À la fin, la zone non triée a disparu et la liste est rangée. La différence entre les deux algorithmes tient à la façon dont on fait passer un élément de la zone non triée vers la zone triée.

Le tri par sélection

ExempleTrace sur la liste [5, 2, 9, 1, 7]

Tour $i$	Zone non triée avant le tour	Minimum trouvé	Liste après l'échange
0	5, 2, 9, 1, 7	1 (indice 3)	1, 2, 9, 5, 7
1	2, 9, 5, 7	2 (indice 1)	1, 2, 9, 5, 7
2	9, 5, 7	5 (indice 3)	1, 2, 5, 9, 7
3	9, 7	7 (indice 4)	1, 2, 5, 7, 9

Au tour 1, le minimum est déjà à sa place : l'échange d'une case avec elle-même ne change rien. Au tour 0, le 5 part à l'indice 3, à la place du 1.

def tri_selection(t):
    n = len(t)
    for i in range(n - 1):
        i_min = i
        for j in range(i + 1, n):
            if t[j] < t[i_min]:
                i_min = j
        t[i], t[i_min] = t[i_min], t[i]

La boucle extérieure choisit la case i à remplir. La boucle intérieure ne fait aucune modification : elle se contente de repérer l'indice du minimum dans la variable i_min. L'échange n'a lieu qu'une fois, à la fin du tour.

Le tri par insertion

ExempleTrace sur la liste [5, 2, 9, 1, 7]

Tour $i$	Clé	Décalages effectués	Liste après l'insertion
1	2	le 5 passe à droite	2, 5, 9, 1, 7
2	9	aucun	2, 5, 9, 1, 7
3	1	9, 5 et 2 passent à droite	1, 2, 5, 9, 7
4	7	le 9 passe à droite	1, 2, 5, 7, 9

Au tour 2, le 9 est plus grand que tout ce qui est à sa gauche : il reste où il est. Au tour 3, le 1 est le plus petit de tous, il traverse donc toute la zone triée.

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

La boucle while remonte vers la gauche tant que l'élément observé est plus grand que la clé. Elle s'arrête dans deux situations : on est sorti de la liste (j vaut -1) ou on a trouvé un élément qui n'est pas plus grand que la clé. Dans les deux cas, la place libre est la case j + 1.

Prouver qu'un tri est correct : l'invariant de boucle

Un programme qui donne le bon résultat sur trois exemples n'est pas forcément correct. Pour être sûr qu'un tri range toutes les listes, on raisonne avec un invariant de boucle. Le programme de Première demande de savoir le décrire et de justifier ainsi la correction des tris par insertion et par sélection.¹

Démonstration · Pourquoi l'invariant de la sélection est vrai

Avant la boucle ( $i = 0$ ) : t[0:0] est vide, donc la propriété est vraie sans rien vérifier.

Conservation : on suppose la propriété vraie au début du tour $i$ . La boucle intérieure trouve le minimum de t[i:]. Ce minimum est supérieur ou égal à tous les éléments déjà placés, puisque ceux-ci sont inférieurs ou égaux à tout le reste. On l'échange avec la case i. La zone t[0:i+1] est donc triée, et ses éléments sont inférieurs ou égaux à ceux de t[i+1:]. La propriété est vraie au début du tour $i+1$ .

À la fin : après le dernier tour, les $n-1$ premières cases sont les plus petites et sont triées. La dernière case contient forcément le plus grand élément. La liste entière est donc triée.

Démonstration · Pourquoi l'invariant de l'insertion est vrai

Avant la boucle ( $i = 1$ ) : t[0:1] ne contient qu'un élément, donc il est trié.

Conservation : on suppose t[0:i] triée. La boucle while décale vers la droite tous les éléments strictement plus grands que cle, en commençant par le plus à droite. Elle s'arrête sur un élément inférieur ou égal à cle, ou au début de la liste. En déposant cle dans la case libérée, on obtient dans t[0:i+1] : d'abord les éléments inférieurs ou égaux à cle, puis cle, puis les éléments plus grands, chaque groupe gardant son ordre. La zone t[0:i+1] est triée.

À la fin : après le tour $i = n-1$ , la zone triée est t[0:n], c'est-à-dire la liste entière.

Le coût des deux algorithmes

Le coût d'un algorithme mesure le travail qu'il demande, souvent en nombre de comparaisons ou d'opérations élémentaires, en fonction de la taille $n$ de la liste. Pour les tris, on compte surtout les comparaisons entre deux éléments et les échanges ou décalages.

Démonstration · Retrouver la formule

Dans le code, au tour $i$ , la boucle intérieure compare la case i_min avec les cases d'indices $i+1$ à $n-1$ . Cela fait $n-1-i$ comparaisons.

Il faut additionner pour $i$ de $0$ à $n-2$ :

$(n-1) + (n-2) + \dots + 2 + 1 = \frac{n(n-1)}{2}.$

Par exemple, pour $n = 5$ : $4 + 3 + 2 + 1 = 10$ comparaisons, ce qui correspond bien à $\frac{5 \times 4}{2}$ .

Comparer, choisir et éviter les pièges

Critère	Tri par sélection	Tri par insertion
Idée	choisir le minimum de la zone non triée	insérer l'élément suivant dans la zone triée
Position des éléments de la zone triée	définitive dès qu'ils sont placés	provisoire, elle peut encore changer
Comparaisons	toujours $\frac{n(n-1)}{2}$	de $n-1$ à $\frac{n(n-1)}{2}$
Liste déjà triée	fait autant de travail que d'habitude	travail minimal
Mouvements	au plus un échange par tour	décalages nombreux possibles

Exercices corrigés

Exercice 1 Compter les comparaisons du tri par sélection

★☆☆Environ 5 min

On trie une liste de 8 nombres avec le tri par sélection écrit dans le cours. Combien de comparaisons entre deux éléments sont effectuées en tout ?

Indice 1

Au premier tour, on compare le candidat minimum avec les 7 autres cases.

Indice 2

À chaque tour, la zone non triée perd une case : additionne 7 + 6 + … + 1.

Voir la correction pas à pas

Au tour 0, la boucle intérieure compare avec les cases d'indices 1 à 7 : 7 comparaisons.
Au tour 1, il reste 6 comparaisons, puis 5, 4, 3, 2 et enfin 1 au tour 6.
La somme vaut $7+6+5+4+3+2+1 = 28$ .
On retrouve la formule $\frac{n(n-1)}{2}$ avec $n = 8$ : $\frac{8 \times 7}{2} = 28$ .

Le tri par sélection d'une liste de 8 éléments demande 28 comparaisons, quel que soit l'ordre des valeurs au départ.

Exercice 2 Dérouler les deux tris sur la même liste

★★☆Environ 10 min

Soit la liste [7, 3, 8, 1, 5].

Donne la liste après les deux premiers tours du tri par sélection.
Donne la liste après les deux premiers tours du tri par insertion (clés d'indices 1 et 2).

Indice 1

Pour la sélection, repère d'abord l'indice du minimum de toute la liste.

Indice 2

Pour l'insertion, la zone triée au départ est seulement la case 0.

Voir la correction pas à pas

Sélection, tour 0 : le minimum de toute la liste est 1, à l'indice 3. On l'échange avec la case 0 : [1, 3, 8, 7, 5].
Sélection, tour 1 : le minimum de [3, 8, 7, 5] est 3, déjà à l'indice 1. L'échange ne change rien : [1, 3, 8, 7, 5].
Insertion, tour 1 : la clé est 3. Le 7 est plus grand, il se décale à droite, et la clé se dépose à l'indice 0 : [3, 7, 8, 1, 5].
Insertion, tour 2 : la clé est 8. Le 7 n'est pas plus grand que 8, donc aucun décalage : [3, 7, 8, 1, 5].

Après deux tours, la sélection donne [1, 3, 8, 7, 5] et l'insertion donne [3, 7, 8, 1, 5]. Les deux zones triées n'ont pas le même sens : en sélection, 1 et 3 sont définitivement placés ; en insertion, 3, 7, 8 sont seulement triés entre eux, et le 1 doit encore arriver à gauche.

Exercice 3 Décalages dans le pire cas de l'insertion

★★★Environ 10 min

On trie par insertion la liste [6, 5, 4, 3, 2, 1], rangée à l'envers.

Combien de décalages d'éléments sont effectués au total ?
Quel est le nombre de décalages pour une liste déjà triée de même taille ?

Indice 1

À chaque tour, la clé est plus petite que tous les éléments déjà triés.

Indice 2

Décompose tour par tour, avec $i$ allant de 1 à 5.

Voir la correction pas à pas

Au tour $i = 1$ , la clé 5 doit passer devant le 6 : 1 décalage.
Au tour $i = 2$ , la clé 4 est plus petite que 5 et 6 : 2 décalages. Et ainsi de suite jusqu'à 5 décalages au tour $i = 5$ .
Le total vaut $1+2+3+4+5 = 15$ , soit $\frac{6 \times 5}{2}$ .
Pour une liste déjà triée, aucune clé n'est plus petite que son voisin de gauche : 0 décalage.

La liste à l'envers de 6 éléments demande 15 décalages, alors qu'une liste déjà triée n'en demande aucun. Cet écart montre pourquoi le coût de l'insertion dépend de la liste de départ.

Exercice 4 Majorer les échanges du tri par sélection

★★☆Environ 5 min

Avec le code tri_selection du cours, quel est le nombre maximal d'échanges t[i], t[i_min] = t[i_min], t[i] exécutés pour une liste de 10 éléments ?

Indice 1

Combien de fois la boucle extérieure s'exécute-t-elle ?

Indice 2

Il y a au plus un échange par tour.

Voir la correction pas à pas

La boucle extérieure est for i in range(n - 1) : avec $n = 10$ , elle fait 9 tours.
Chaque tour exécute exactement une instruction d'échange.
Le nombre maximal d'échanges est donc $10 - 1 = 9$ .

Le tri par sélection d'une liste de 10 éléments fait au plus 9 échanges, contre 45 comparaisons. Le nombre d'échanges est proportionnel à $n$ , alors que celui des comparaisons est quadratique.

Les questions qu'on se pose

Quelle est la vraie différence entre tri par sélection et tri par insertion ?

Le tri par sélection choisit, parmi les éléments non triés, le plus petit, et le met à sa place définitive.⁴ Le tri par insertion prend l'élément suivant, quel qu'il soit, et le glisse à la bonne position parmi les éléments déjà triés. Dans le premier, la zone de gauche est définitive ; dans le second, elle est triée mais provisoire.

Lequel des deux tris est le plus rapide ?

Dans le pire cas, ils sont tous deux quadratiques.⁶ Mais le tri par insertion peut être plus rapide sur certaines listes, notamment quand elles sont déjà presque triées, alors que le tri par sélection fait toujours le même nombre de comparaisons.⁶ Pour de très grandes listes, on préfère des algorithmes plus efficaces, de l'ordre de $n \log n$ .⁶

Que dois-je savoir faire sur ces tris en NSI ?

Tu dois connaître les deux algorithmes, les appliquer à la main sur un exemple donné et les écrire en Python.⁵ Tu dois aussi savoir justifier leur correction avec un invariant de boucle et savoir que leur coût est quadratique dans le pire cas.¹

Comment trouver un invariant de boucle ?

Pose-toi la question : qu'est-ce qui est vrai de la zone déjà traitée au début de chaque tour ? Pour la sélection, la zone t[0:i] est triée et contient les plus petits éléments. Pour l'insertion, t[0:i] est triée. Vérifie ensuite trois choses : c'est vrai avant la boucle, un tour conserve la propriété, et à la fin la propriété donne le résultat voulu.

Pourquoi la boucle du tri par sélection s'arrête-t-elle à n - 2 ?

Quand il ne reste qu'une case non triée, tous les autres éléments sont déjà placés et inférieurs ou égaux à elle. Elle est donc forcément à la bonne position. Un tour supplémentaire ne ferait que comparer cette case avec rien, donc range(n - 1) suffit.

Sources

Programme visé : Programme de numérique et sciences informatiques de première générale · Ministère de l'Éducation nationale

Programme de numérique et sciences informatiques de première générale, Ministère de l'Éducation nationale. Consulté le 7 novembre 2026.
Les tris - Ressource Lumni/Éduscol (notion de tri, exercices), Éduscol / Lumni. Consulté le 7 novembre 2026.
Algorithmique - Ressource Éduscol, Éduscol. Consulté le 7 novembre 2026.
Ressources algorithmique - Document de référence Éduscol, Ministère de l'Éducation nationale - Éduscol. Consulté le 7 novembre 2026.
Fiche pratique - Tri par insertion et tri par sélection, Pixees (ressources NSI). Consulté le 7 novembre 2026.
Tri par sélection, Wikipédia. Consulté le 7 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

Tris par insertion et par sélection : cours de Première NSI

L'essentiel

Pourquoi trier une liste ?

Ce qu'est un algorithme de tri

Le tri par sélection

Le tri par insertion

Prouver qu'un tri est correct : l'invariant de boucle

Le coût des deux algorithmes

Comparer, choisir et éviter les pièges

Exercices corrigés

Exercice 1 Compter les comparaisons du tri par sélection

Exercice 2 Dérouler les deux tris sur la même liste

Exercice 3 Décalages dans le pire cas de l'insertion

Exercice 4 Majorer les échanges du tri par sélection

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur