Tris par insertion et par sélection : fiche 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 à la suite de la partie triée ; il fait toujours 2n(n−1) comparaisons 6.
Le tri par insertion prend chaque élément à son tour et le glisse à sa place dans la partie déjà triée à sa gauche.
Les deux tris sont en place et leur coût est quadratique dans le pire cas 16.
Le programme demande de savoir les dérouler sur un exemple, les écrire en Python et justifier leur correction par un invariant de boucle15.
Ce qu'il faut savoir faire
Au programme de première, ces deux algorithmes se présentent ensemble. Tu dois pouvoir les dérouler à la main sur un exemple, les programmer en Python, et justifier qu'ils trient correctement en décrivant un invariant de boucle 15. On sait aussi que leur coût est quadratique dans le pire cas 1.
Le tri par sélection
def tri_selection(t):
n = len(t)
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if t[j] < t[p]:
p = j
t[i], t[p] = t[p], t[i]
La variable p garde l'indice du plus petit élément rencontré. Un seul échange a lieu par tour.
Le tri par insertion
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 décale les éléments plus grands que cle. Le test j >= 0 doit venir avantt[j] > cle pour ne pas sortir du tableau.
Justifier : l'invariant de boucle
Comparer les deux tris
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
Le tri par sélection fait toujours 2n(n−1) comparaisons 6. Pour n=5 : 25×4=10. Écrire 5×4=20 oublie la division par deux, car on ne compare chaque paire qu'une fois.
À chaque tour, on place le minimum de la partie non triée juste après la partie triée 4 : les premières cases contiennent donc les plus petits éléments, définitivement placés. La deuxième réponse décrit l'invariant du tri par insertion, pas celui de la sélection.
Vrai : on libère ainsi la place où déposer cle. Sans ces décalages, on écraserait des valeurs du tableau. Le tri par insertion ne cherche pas de minimum : c'est la confusion avec la sélection.
Ces deux tris ont un coût quadratique dans le pire cas 16. Le coût linéaire ne concerne que le nombre d'échanges de la sélection 6, pas le nombre total d'opérations.
Les questions qu'on se pose
Quel tri est le meilleur, insertion ou sélection ?
Tous deux sont quadratiques dans le pire cas 1. Le tri par sélection est même jugé moins bon que le tri par insertion, qui peut être plus rapide sur certaines entrées 6. Un avantage de la sélection : elle limite le nombre d'échanges 6.
Pourquoi `range(n - 1)` dans le tri par sélection ?
Quand il ne reste qu'une case non triée, ce dernier élément est forcément le plus grand : il est déjà à sa place. Le tour i = n - 1 serait donc inutile.
Que faut-il savoir faire à l'examen sur ces tris ?
Le programme attend que tu saches dérouler les algorithmes sur un exemple, les écrire en Python 5 et justifier leur correction par un invariant de boucle 1. Entraîne-toi à écrire les deux codes de mémoire, avec les bornes des boucles.