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

Tris par insertion et par sélection : exercices de 1re NSI

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

L'essentiel

Le tri par sélection cherche le minimum de la partie non triée et le place à sa position ; il fait toujours $\frac{n(n-1)}{2}$ comparaisons ⁶.
Le tri par insertion prend chaque élément à son tour et le glisse à sa place dans la partie gauche déjà triée.
Les deux tris sont quadratiques dans le pire cas ; l'insertion peut être plus rapide sur certaines entrées, par exemple une liste presque triée ⁶.
Le tri par sélection fait au plus un nombre linéaire d'échanges ⁶.
Pour prouver qu'un tri est correct, on énonce un invariant de boucle et on le justifie ¹.

Comment utiliser ces exercices

Les exercices vont du plus simple au plus difficile. Les premiers te font dérouler les deux algorithmes à la main, sur de petites listes. Les suivants te demandent de compter des opérations, de compléter du code Python, puis de justifier qu'un tri est correct. Prends une feuille, écris l'état de la liste après chaque étape, et ne regarde les indices qu'après avoir cherché quelques minutes.

Les exercices

Exercice 1 Dérouler le tri par sélection

★☆☆Environ 8 min

On trie la liste L = [7, 3, 9, 1, 5] dans l'ordre croissant avec le tri par sélection.

Écris l'état de la liste à la fin de chaque tour de la boucle extérieure, en précisant l'indice du minimum trouvé.

Indice 1

Au premier tour, la partie non triée est la liste entière : cherche son plus petit élément.

Indice 2

Si le minimum est déjà à la bonne place, l'échange ne change rien.

Voir la correction pas à pas

Tour 0 : la partie non triée est [7, 3, 9, 1, 5]. Le minimum est 1, à l'indice 3. On l'échange avec l'élément d'indice 0 : [1, 3, 9, 7, 5].
Tour 1 : la partie non triée commence à l'indice 1 : [3, 9, 7, 5]. Le minimum est 3, déjà à l'indice 1. Rien ne bouge : [1, 3, 9, 7, 5].
Tour 2 : la partie non triée est [9, 7, 5]. Le minimum est 5, à l'indice 4. On l'échange avec l'indice 2 : [1, 3, 5, 7, 9].
Tour 3 : la partie non triée est [7, 9]. Le minimum est 7, déjà à l'indice 3. La liste reste [1, 3, 5, 7, 9].
Il n'y a plus qu'un élément non trié, qui est forcément à sa place : la liste est triée.

Résultat : [1, 3, 5, 7, 9], obtenu avec seulement 2 échanges réels. Le tri par sélection fait peu d'échanges, mais beaucoup de comparaisons ⁶.

Exercice 2 Dérouler le tri par insertion

★☆☆Environ 8 min

On trie la liste L = [4, 2, 7, 1, 3] dans l'ordre croissant avec le tri par insertion.

Écris la liste après l'insertion de chaque élément, en soulignant mentalement la partie déjà triée à gauche.

Indice 1

Au départ, la partie triée est réduite à [4].

Indice 2

Pour chaque nouvel élément, décale vers la droite tous les éléments de la partie triée qui sont plus grands que lui.

Voir la correction pas à pas

Départ : partie triée [4], reste à insérer 2, 7, 1, 3.
Insertion de 2 : 4 est plus grand, il se décale d'une case. On obtient [2, 4, 7, 1, 3].
Insertion de 7 : 4 n'est pas plus grand que 7, aucun décalage. La liste reste [2, 4, 7, 1, 3].
Insertion de 1 : 7, 4 et 2 sont tous plus grands, ils se décalent. On obtient [1, 2, 4, 7, 3].
Insertion de 3 : 7 et 4 se décalent, 2 est plus petit que 3. On obtient [1, 2, 3, 4, 7].

Résultat : [1, 2, 3, 4, 7]. Remarque qu'à chaque étape, la partie gauche de la liste est triée, même si elle ne contient pas encore tous les éléments.

Exercice 3 Compter les comparaisons du tri par sélection

★☆☆Environ 6 min

Pour une liste de $n$ éléments, le tri par sélection effectue $\frac{n(n-1)}{2}$ comparaisons, quel que soit le contenu de la liste ⁶.

Combien de comparaisons effectue-t-il pour une liste de $10$ éléments ?
Retrouve ce résultat en additionnant les comparaisons de chaque tour : au tour $0$ , on compare le minimum provisoire aux $9$ autres éléments.

Indice 1

Au tour $i$ , la partie non triée contient $n-i$ éléments, donc on fait $n-i-1$ comparaisons.

Indice 2

Additionne $9+8+7+\dots+1$ .

Voir la correction pas à pas

Applique la formule avec $n=10$ : $\frac{10\times 9}{2}=45$ .
Vérifie par la somme des tours : $9+8+7+6+5+4+3+2+1$ .
Regroupe les termes par paires : $(9+1)+(8+2)+(7+3)+(6+4)+5=4\times 10+5=45$ .
Les deux méthodes donnent le même nombre.

Le tri par sélection d'une liste de 10 éléments fait 45 comparaisons, même si la liste est déjà triée. C'est ce qui rend ce tri peu intéressant sur des listes presque triées.

Exercice 4 Compléter le tri par sélection en Python

★★☆Environ 12 min

Voici une fonction de tri par sélection dont trois lignes sont à compléter (repérées par ...).

def tri_selection(t):
    n = len(t)
    for i in range(n - 1):
        m = i                      # indice du minimum provisoire
        for j in range(..., n):    # (a)
            if t[j] < t[m]:
                ...                # (b)
        t[i], t[m] = ..., ...      # (c)

Complète les lignes (a), (b) et (c).
Pourquoi la boucle extérieure s'arrête-t-elle à n - 2 et non à n - 1 ?
Que renvoie la fonction, et que devient la liste passée en paramètre ?

Indice 1

La boucle intérieure ne regarde que la partie non triée, qui commence juste après l'indice i.

Indice 2

L'échange en Python s'écrit a, b = b, a.

Voir la correction pas à pas

(a) : la partie non triée commence à i, et t[i] sert déjà de minimum provisoire. On parcourt donc les indices suivants : range(i + 1, n).
(b) : quand on trouve une valeur plus petite que le minimum provisoire, on retient son indice : m = j.
(c) : on place le minimum à la position i par un échange : t[i], t[m] = t[m], t[i].
Quand i vaut n - 1, la partie non triée ne contient qu'un seul élément, qui est forcément le plus grand et déjà à sa place. Inutile de faire un tour de plus.
La fonction ne contient pas de return : elle renvoie None. La liste est modifiée directement, car le tri se fait sur place ⁶.

Le code complet utilise range(i + 1, n), m = j et t[i], t[m] = t[m], t[i]. Après l'appel tri_selection(L), c'est L elle-même qui est triée.

Exercice 5 Compter les échanges sur une liste inversée

★★☆Environ 10 min

On applique le tri par sélection de l'exercice précédent à la liste [5, 4, 3, 2, 1], qui est triée en ordre décroissant.

On compte un échange seulement quand le minimum trouvé n'est pas déjà à la position i (si m == i, on ne fait rien). Combien d'échanges sont réalisés ?

Indice 1

Déroule les tours un par un, comme dans l'exercice 1.

Indice 2

Remarque qu'après deux échanges bien choisis, la liste est déjà triée.

Voir la correction pas à pas

Tour 0 : le minimum est 1, à l'indice 4. Échange avec l'indice 0 : [1, 4, 3, 2, 5]. Premier échange.
Tour 1 : la partie non triée est [4, 3, 2, 5]. Le minimum est 2, à l'indice 3. Échange avec l'indice 1 : [1, 2, 3, 4, 5]. Deuxième échange.
Tour 2 : le minimum de [3, 4, 5] est 3, déjà à l'indice 2. Pas d'échange.
Tour 3 : le minimum de [4, 5] est 4, déjà à l'indice 3. Pas d'échange.
On compte 2 échanges. Pour une liste inversée de $n$ éléments, on échange les éléments par paires symétriques, ce qui donne $\lfloor n/2\rfloor$ échanges : ici $\lfloor 5/2\rfloor=2$ .

Il y a 2 échanges pour 5 éléments, alors que le nombre de comparaisons vaut 10. Dans tous les cas, le nombre d'échanges du tri par sélection reste au plus linéaire en $n$ ⁶.

Exercice 6 Compter les décalages du tri par insertion

★★☆Environ 12 min

Reprends la liste [4, 2, 7, 1, 3] de l'exercice 2. Dans le tri par insertion, un décalage est le déplacement d'un élément de la partie triée d'une case vers la droite.

Combien de décalages sont effectués à chaque insertion ?
Quel est le total pour cette liste ?

Indice 1

Reprends la trace de l'exercice 2 : le nombre de décalages est le nombre d'éléments plus grands que l'élément inséré dans la partie triée.

Indice 2

Additionne les quatre insertions (2, 7, 1, 3).

Voir la correction pas à pas

Insertion de 2 dans [4] : 4 est plus grand, donc 1 décalage.
Insertion de 7 dans [2, 4] : aucun élément plus grand, donc 0 décalage.
Insertion de 1 dans [2, 4, 7] : les trois éléments sont plus grands, donc 3 décalages.
Insertion de 3 dans [1, 2, 4, 7] : 4 et 7 sont plus grands, donc 2 décalages.
Total : $1+0+3+2=6$ décalages.

Le total est de 6 décalages. Ce nombre mesure à quel point la liste est désordonnée : une liste déjà triée n'en demande aucun, une liste inversée en demande le maximum.

Exercice 7 Liste déjà triée : insertion contre sélection

★★☆Environ 12 min

On trie une liste de $100$ éléments déjà triée dans l'ordre croissant.

Dans le tri par insertion, chaque élément à insérer est comparé à son voisin de gauche ; si celui-ci n'est pas plus grand, l'insertion s'arrête aussitôt.

Combien de comparaisons le tri par insertion effectue-t-il ?
Combien le tri par sélection en effectue-t-il ?
Quelle différence obtient-on, et que peut-on en conclure ?

Indice 1

Le premier élément n'a besoin d'aucune comparaison : il reste seul.

Indice 2

Pour la sélection, applique directement la formule du nombre de comparaisons ⁶.

Voir la correction pas à pas

Insertion : les $99$ éléments suivants le premier sont chacun comparés une seule fois à leur voisin de gauche, puis laissés en place. Cela fait $100-1=99$ comparaisons.
Sélection : le nombre de comparaisons ne dépend pas de l'ordre initial, il vaut $\frac{100\times 99}{2}=4950$ ⁶.
Différence : $4950-99=4851$ comparaisons de plus pour la sélection.
Les deux tris sont quadratiques dans le pire cas, mais l'insertion peut être plus rapide sur certaines entrées particulières ⁶. Une liste déjà triée en est l'exemple le plus net.

Sur une liste triée de 100 éléments, l'insertion fait 99 comparaisons et la sélection 4950, soit 4851 de plus. Le choix d'un tri dépend donc aussi de l'état dans lequel les données arrivent.

Exercice 8 Prévoir une durée avec un coût quadratique

★★★Environ 10 min

Le coût du tri par sélection est quadratique : il croît comme le carré du nombre $n$ d'éléments ⁶. On suppose que la durée d'exécution est proportionnelle au nombre de comparaisons, avec $n$ assez grand pour négliger le terme en $n$ .

Un programme trie $2000$ éléments en $4$ secondes. Combien de temps faudra-t-il environ pour trier $4000$ éléments ?

Indice 1

Si $n$ est multiplié par $k$ , le nombre de comparaisons est environ multiplié par $k^2$ .

Indice 2

Ici, $k$ vaut $2$ .

Voir la correction pas à pas

Le rapport des tailles est $k=\frac{4000}{2000}=2$ .
Le coût quadratique est multiplié par $k^2=4$ .
La durée estimée est donc $4\times 4=16$ secondes.
Ce n'est qu'une estimation : le temps réel dépend aussi de la machine et du reste du programme. Elle montre surtout qu'on ne peut pas se contenter de doubler le temps quand on double la taille.

Doubler la taille de la liste multiplie par quatre la durée : on attend environ 16 secondes. C'est la raison pour laquelle les tris quadratiques sont jugés inefficaces sur de grandes listes, face aux meilleurs algorithmes en $O(n\log n)$ ⁶.

Exercice 9 Invariant de boucle du tri par sélection

★★★Environ 20 min

Le programme de Première demande de savoir décrire un invariant de boucle pour justifier qu'un tri est correct ¹. On reprend tri_selection de l'exercice 4, et on note $t_0$ la liste au départ de la fonction.

Propose un invariant pour la boucle extérieure, à vérifier au début de chaque tour $i$ .
Montre qu'il est vrai avant le premier tour.
Montre qu'un tour le conserve.
Conclus sur l'état de la liste en fin de fonction.

Indice 1

Pense à ce que contient la partie gauche de la liste, de l'indice $0$ à $i-1$ .

Indice 2

Pour la conservation, utilise le fait que le minimum de la partie non triée est au moins aussi grand que tout ce qui est déjà placé à gauche.

Voir la correction pas à pas

Invariant. Au début du tour $i$ , les cases d'indices $0$ à $i-1$ contiennent, rangés dans l'ordre croissant, les $i$ plus petits éléments de $t_0$ .
Initialisation. Avant le tour $0$ , la partie $0$ à $-1$ est vide : l'énoncé est vrai sans rien vérifier.
Conservation. Au tour $i$ , la boucle intérieure trouve le minimum de la partie d'indices $i$ à $n-1$ . Par l'invariant, tous les éléments de cette partie sont plus grands ou égaux à ceux déjà placés à gauche. Après l'échange, le minimum est à l'indice $i$ , à droite des éléments déjà triés et supérieur ou égal à chacun d'eux : les $i+1$ premières cases contiennent donc les $i+1$ plus petits éléments, dans l'ordre. L'invariant est vrai au début du tour $i+1$ .
Terminaison. La boucle s'arrête quand $i$ atteint $n-1$ . L'invariant donne alors les $n-1$ plus petits éléments triés dans les cases $0$ à $n-2$ .
Conclusion. La dernière case contient le seul élément restant, qui est le plus grand : la liste entière est triée, et elle contient les mêmes éléments que $t_0$ puisqu'on n'a fait que des échanges.

L'invariant, vrai au départ et conservé à chaque tour, prouve que tri_selection produit bien une liste triée. Pour le tri par insertion, le raisonnement est analogue avec l'invariant « les cases $0$ à $i-1$ contiennent les éléments de départ de ces cases, dans l'ordre croissant ».

Les questions qu'on se pose

Quel tri choisir entre insertion et sélection ?

Les deux sont quadratiques dans le pire cas ⁶. Le tri par insertion est souvent plus rapide quand la liste est déjà presque triée, car il fait peu de décalages. Le tri par sélection a un avantage précis : il réalise au plus un nombre linéaire d'échanges ⁶, ce qui compte si déplacer un élément coûte cher. Pour des listes très grandes, aucun des deux n'est adapté : les meilleurs algorithmes s'exécutent en $O(n\log n)$ ⁶.

Que faut-il savoir faire à l'examen sur ces deux tris ?

Il faut connaître les deux algorithmes, les dérouler à la main sur un exemple donné et les écrire en Python ⁵. Le programme demande aussi de pouvoir justifier la correction d'un tri par un invariant de boucle, et de savoir que le coût de ces tris est quadratique dans le pire cas ¹. Entraîne-toi donc à tracer, à compter des opérations et à énoncer un invariant.

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 : exercices de 1re NSI

L'essentiel

Comment utiliser ces exercices

Les exercices

Exercice 1 Dérouler le tri par sélection

Exercice 2 Dérouler le tri par insertion

Exercice 3 Compter les comparaisons du tri par sélection

Exercice 4 Compléter le tri par sélection en Python

Exercice 5 Compter les échanges sur une liste inversée

Exercice 6 Compter les décalages du tri par insertion

Exercice 7 Liste déjà triée : insertion contre sélection

Exercice 8 Prévoir une durée avec un coût quadratique

Exercice 9 Invariant de boucle du tri par sélection

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur