Tri par insertion et par sélection

Vue d'ensemble

Ranger une liste dans l'ordre croissant : c'est le premier vrai algorithme non trivial de la prépa. Deux méthodes sont explicitement au programme de première année — le tri par sélection et le tri par insertion. Elles trient toutes deux sur place en temps $O (n^{2})$ , mais elles ne se ressemblent pas : l'une fait toujours le même travail quel que soit l'ordre de départ, l'autre devient très rapide quand la liste est presque triée. Comprendre cette différence, savoir tracer chaque algorithme à la main et énoncer son invariant de boucle : voilà ce qu'un concours attend de vous.

Au programme (BO 2021). Algorithmes de tri par insertion et par sélection ; notion de tri en place ; coût d'un algorithme et comparaison de complexités ; invariant de boucle pour justifier la correction. Le tri fusion

O (n lo g n)

relève de la partie « diviser pour régner » et n'est cité ici qu'en ouverture.

Prérequis

Boucles for et while, boucles imbriquées (fiche boucles-for-while).
Listes Python : indexation t[i], longueur len(t), affectation d'une case, échange t[i], t[j] = t[j], t[i] (fiche listes-chaines).
Notation de Landau $O (\cdot)$ et comptage d'opérations (fiche complexite-temporelle).
Notion d'invariant de boucle (fiche correction-terminaison).

🎯 Accompagnement Majorant

Le tri, c'est le chapitre où l'on apprend à raisonner sur un algorithme, pas seulement à l'écrire. Si les invariants de boucle et le comptage de comparaisons vous glissent entre les doigts, nos mentors alumni X · Centrale · Mines vous font tracer les algorithmes à la main jusqu'à ce que le déclic vienne.

Trouver un mentor →

Le cadre : trier une liste en place

Dans toute cette fiche, t est une liste Python de $n$ nombres, et « trier » signifie la réorganiser pour que t[0] <= t[1] <= ... <= t[n-1]. Les deux tris étudiés partagent une propriété importante : ils ne créent pas de nouvelle liste, ils déplacent les éléments à l'intérieur de t.

Définition 1.1 — Tri en place

Un tri est dit en place (in situ) s'il trie la liste en n'utilisant qu'un nombre constant de cases mémoire supplémentaires (quelques variables : un compteur, un indice, une variable d'échange), indépendamment de $n$ . Il ne recopie pas la liste dans une seconde liste de taille $n$ .

Définition 1.2 — Tri stable

Un tri est stable s'il conserve l'ordre relatif de deux éléments de même valeur : si deux éléments égaux apparaissent dans un certain ordre au départ, ils restent dans cet ordre à l'arrivée. Le tri par insertion est stable ; le tri par sélection tel qu'on l'écrit ici ne l'est pas (un échange lointain peut faire « sauter » un élément par-dessus son égal).

📝 Pourquoi mesurer en comparaisons ? Pour un tri, l'opération qui coûte est la comparaison de deux éléments (le test t[j] < t[imin]). On compte donc le nombre de comparaisons en fonction de

n

: c'est ce nombre qui donne la complexité en

O (\cdot)

Tri par sélection

Idée. Le plus petit élément de la liste doit finir en case 0. On le cherche, on l'y met. Le deuxième plus petit doit finir en case 1 : on cherche le minimum de ce qui reste (les cases 1 à $n - 1$ ), on l'y met. Et ainsi de suite. À chaque tour, on sélectionne le minimum du reste non trié et on l'échange avec la première case encore non triée.

📝 Invariant de boucle. Juste avant le tour d'indice

i

, le sous-tableau t[0..i-1] est trié ET contient les

i

plus petits éléments de la liste, à leur place définitive. C'est ce dernier point (« les plus petits, à leur place définitive ») qui distingue la sélection de l'insertion : une fois posé, un élément ne bouge plus jamais.

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

🔍 Décryptage ligne par ligne

n = len(t)On mémorise la longueur une fois pour toutes, pour piloter les boucles.

for i in range(n):

i

est la case que l'on va remplir définitivement à ce tour : d'abord la 0, puis la 1, etc. Tout ce qui est avant

i

est déjà trié et posé.

imin = iOn suppose provisoirement que le minimum du reste (cases

i

n - 1

) se trouve en case

i

. imin retient l'indice du plus petit trouvé jusqu'ici.

for j in range(i + 1, n):On balaie toutes les cases situées après

i

pour vérifier cette supposition.

if t[j] < t[imin]: imin = jSi on rencontre une valeur strictement plus petite que le minimum courant, elle devient le nouveau candidat : on retient son indice

j

t[i], t[imin] = t[imin], t[i]À la fin du balayage, t[imin] est le vrai minimum du reste. On l'échange avec la case

i

: il est désormais à sa place définitive. (Si imin == i, l'échange ne change rien, ce n'est pas un problème.)

return tLa liste a été modifiée en place ; on la renvoie par commodité.

Trace du tri par sélection sur `[5, 2, 4, 1]` — état après l'échange de chaque tour
Tour $i$	Reste balayé (cases $i$ ..3)	Minimum trouvé (indice `imin`)	Échange	Liste après le tour
0	5, 2, 4, 1	1 (indice 3)	`t[0]`↔`t[3]`	`[1, 2, 4, 5]`
1	2, 4, 5	2 (indice 1)	`t[1]`↔`t[1]`	`[1, 2, 4, 5]`
2	4, 5	4 (indice 2)	`t[2]`↔`t[2]`	`[1, 2, 4, 5]`
3	5	5 (indice 3)	aucun	`[1, 2, 4, 5]` ✓ trié

⚠ Le tri par sélection travaille toujours autant. Même si la liste est déjà triée, la boucle interne balaie tout le reste à chaque tour : elle ne « voit » pas que c'est inutile. Le nombre de comparaisons ne dépend donc PAS de l'ordre initial. C'est le gros défaut de ce tri.

Combien de comparaisons ?

Comptons les tests t[j] < t[imin]. Au tour $i$ , la boucle interne va de $i + 1$ à $n - 1$ , soit $n - 1 - i$ comparaisons.

Propriété 2.1 — Nombre exact de comparaisons du tri par sélection ★ À savoir démontrer

Sur une liste de $n$ éléments, le tri par sélection ci-dessus effectue exactement $\frac{n ( n - 1 )}{2}$ comparaisons, quel que soit l'ordre initial de la liste. Sa complexité temporelle est donc $Θ (n^{2})$ , dans tous les cas (meilleur, moyen, pire).

Démonstration

Notons $C$ le nombre total de comparaisons. Au tour d'indice $i$ (avec $i$ allant de $0$ à $n - 1$ ), la boucle interne for j in range(i+1, n) exécute une comparaison pour chaque valeur de $j$ de $i + 1$ à $n - 1$ , c'est-à-dire $n - 1 - i$ comparaisons. En sommant sur tous les tours :

$C = i = 0 \sum n - 1 (n - 1 - i) .$

Posons le changement d'indice $k = n - 1 - i$ . Quand $i$ parcourt $0, 1, \dots, n - 1$ , l'entier $k$ parcourt $n - 1, n - 2, \dots, 0$ . Donc

$C = k = 0 \sum n - 1 k = 0 + 1 + 2 + \dots + (n - 1) = \frac{( n - 1 ) n}{2} .$

On reconnaît la somme des premiers entiers. Aucune ligne de ce calcul ne dépend des valeurs contenues dans t : le nombre de comparaisons est le même pour une liste triée, triée à l'envers ou quelconque. D'où $C = \frac{n ( n - 1 )}{2} \sim \frac{n ^{2}}{2}$ , et la complexité $Θ (n^{2})$ . $■$

💡 Vérification. Pour

n = 4

\frac{4 \times 3}{2} = 6

comparaisons. On les recompte sur les tours :

3 + 2 + 1 + 0 = 6

. Pour

n = 10

\frac{10 \times 9}{2} = 45

Tri par insertion

Idée. C'est le tri du joueur de cartes : on prend les cartes une par une et on insère chaque nouvelle carte à sa place dans la main déjà triée. On parcourt la liste de gauche à droite ; à chaque étape, la partie à gauche est déjà triée, et on y insère le nouvel élément en le faisant reculer par décalages successifs.

📝 Invariant de boucle. Juste avant le tour d'indice

i

, le sous-tableau t[0..i-1] est trié (mais, contrairement à la sélection, il ne contient pas forcément les plus petits éléments : ce ne sont que les

i

premiers éléments rencontrés, rangés entre eux). Le tour

i

insère t[i] à la bonne place dans cette partie triée.

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

🔍 Décryptage ligne par ligne

for i in range(1, n):On commence à 1 : la case 0, seule, est déjà « triée ».

i

est l'élément que l'on va insérer dans la partie gauche t[0..i-1].

x = t[i]On met de côté la valeur à insérer dans x. Indispensable : on va écraser t[i] pendant les décalages, il faut donc en garder une copie.

j = i - 1j pointe sur le dernier élément de la partie triée ; on va remonter vers la gauche à partir de là.

while j >= 0 and t[j] > x:Tant qu'on n'a pas dépassé le début (j >= 0) ET que l'élément examiné est plus grand que x, il doit passer à droite de x. Le test j >= 0 d'abord empêche de lire une case inexistante (court-circuit du and).

t[j + 1] = t[j]On décale t[j] d'une case vers la droite pour faire de la place. La case t[j] devient un « trou » qu'on comblera.

j = j - 1On recule d'un cran pour examiner l'élément précédent.

t[j + 1] = xLa boucle s'est arrêtée : soit on est au bord (j == -1), soit t[j] <= x. Dans les deux cas, la bonne place de x est j+1 (le trou courant). On y dépose x.

Trace du tri par insertion sur `[5, 2, 4, 1]` — insertion de chaque nouvel élément
Tour $i$	Valeur insérée `x`	Décalages effectués	Liste après insertion
1	2	5 recule d'une case (1 décalage)	`[2, 5, 4, 1]`
2	4	5 recule ; 2 reste (2 ≤ 4) — 1 décalage	`[2, 4, 5, 1]`
3	1	5, 4, 2 reculent tous (3 décalages)	`[1, 2, 4, 5]` ✓ trié

⚠ Ne pas oublier de sauvegarder x. Si on écrivait t[j+1] = t[j] sans avoir copié t[i] dans x au préalable, on écraserait dès le premier décalage la valeur qu'on voulait insérer. La ligne x = t[i] est le cœur de l'algorithme.

Meilleur cas, pire cas : la différence clé

Ici, le nombre de décalages dépend de l'ordre initial, car la boucle while s'arrête dès qu'elle trouve un élément $\leq x$ .

Meilleur cas — liste déjà triée. À chaque tour, t[j] <= x immédiatement : la boucle while ne s'exécute jamais, on fait une seule comparaison par tour. Total $\sim n$ comparaisons : complexité $O (n)$ , linéaire.
Pire cas — liste triée à l'envers. Chaque nouvel élément est plus petit que tous ceux de gauche : il faut les décaler tous. Au tour $i$ , cela fait $i$ décalages, soit au total $1 + 2 + \dots + (n - 1) = \frac{n ( n - 1 )}{2}$ : complexité $O (n^{2})$ .

Propriété 3.1 — Complexité du tri par insertion

Le tri par insertion est en $O (n)$ dans le meilleur cas (liste déjà triée) et en $O (n^{2})$ dans le pire cas (liste triée à l'envers) ; en moyenne il est aussi en $Θ (n^{2})$ . Il est particulièrement efficace sur des listes presque triées, où il s'approche du comportement linéaire.

🎯 Accompagnement Majorant

« Meilleur cas », « pire cas » : ces mots piègent la moitié des copies. Savoir construire soi-même l'entrée qui déclenche le pire cas est un réflexe d'oral. Nos mentors alumni X · Centrale · Mines vous entraînent sur ce type de raisonnement.

Trouver un mentor →

Comparer les deux tris

Les deux tris sont en place et de complexité $O (n^{2})$ , mais leur comportement diffère. Le tableau ci-dessous résume ce qu'il faut retenir.

Sélection contre insertion
Critère	Tri par sélection	Tri par insertion
Comparaisons (meilleur cas)	$\frac{n ( n - 1 )}{2}$ — $Θ (n^{2})$	$\sim n$ — $O (n)$
Comparaisons (pire cas)	$\frac{n ( n - 1 )}{2}$ — $Θ (n^{2})$	$\frac{n ( n - 1 )}{2}$ — $O (n^{2})$
Sensible à l'ordre initial ?	Non (toujours pareil)	Oui (rapide si presque trié)
En place ?	Oui	Oui
Stable ?	Non	Oui
Nombre d'échanges/déplacements	Peu d'échanges ( $\leq n - 1$ )	Beaucoup de décalages possibles

📐 Méthode — Lequel choisir à l'examen ?

Si la question demande un tri simple et un nombre de comparaisons garanti indépendant des données : tri par sélection.
Si la liste est déjà presque triée (données quasi ordonnées, insertion d'un élément dans une liste triée) : tri par insertion, qui exploite l'ordre existant.
Si l'énoncé exige mieux que $O (n^{2})$ sur de grandes listes : il faut un tri « diviser pour régner » comme le tri fusion (voir ci-dessous).

Ouverture : le tri fusion en O(n log n)

Les deux tris de cette fiche plafonnent à $O (n^{2})$ , ce qui devient trop lent dès que $n$ atteint quelques milliers. Le tri fusion (merge sort) fait mieux : il coupe la liste en deux moitiés, trie chacune récursivement, puis fusionne les deux moitiés triées en un seul parcours. Cette stratégie « diviser pour régner » donne une complexité $O (n lo g n)$ , bien plus rapide. On ne le code pas ici : il repose sur la récursivité (fiche recursivite) et sur la justification du $lo g n$ par un arbre de découpage. Retenez seulement le résultat et l'idée.

📝 Correction et invariant. Prouver qu'un tri est correct, c'est exhiber son invariant de boucle et montrer qu'il est vrai avant la première itération, préservé à chaque tour, et qu'à la fin il entraîne « la liste entière est triée ». C'est exactement la méthode de la fiche correction-terminaison, appliquée aux invariants énoncés plus haut.

Exercices corrigés

Exo 1Une étape de sélection à la mainFacile

On applique le tri par sélection à la liste [7, 3, 5, 2]. Donner l'état de la liste après le tout premier tour de la boucle externe (tour $i = 0$ ), puis le nombre total de comparaisons qu'effectuera l'algorithme jusqu'à la fin.

Voir la correction détaillée

Tour

i = 0

: on cherche le minimum des cases 0 à 3, c'est-à-dire de 7, 3, 5, 2. Le minimum est 2, en indice 3. On l'échange avec la case 0.

Résultat après le tour : [2, 3, 5, 7]. (Ici la liste se trouve déjà triée, mais l'algorithme ne le sait pas et continuera.)

Nombre total de comparaisons :

n = 4

, donc

\frac{n ( n - 1 )}{2} = \frac{4 \times 3}{2} = 6

, quel que soit l'ordre de départ. L'algorithme fera bien 6 comparaisons même si la liste est déjà triée après le premier tour.

Exo 2Compter les décalages en insertionIntermédiaire

On trie [4, 3, 2, 1] par insertion. Combien de décalages (exécutions de la ligne t[j+1] = t[j]) l'algorithme effectue-t-il au total ? Et sur [1, 2, 3, 4] ? Qu'est-ce que cela illustre ?

Voir la correction détaillée

Sur [4, 3, 2, 1] (trié à l'envers, c'est le pire cas) : au tour

i = 1

, 3 passe devant 4 → 1 décalage. Au tour

i = 2

, 2 passe devant 4 et 3 → 2 décalages. Au tour

i = 3

, 1 passe devant 4, 3, 2 → 3 décalages.

Total :

1 + 2 + 3 = 6

décalages, soit

\frac{n ( n - 1 )}{2}

avec

n = 4

. C'est le comportement

O (n^{2})

du pire cas.

Sur [1, 2, 3, 4] (déjà trié, meilleur cas) : à chaque tour t[j] <= x immédiatement, la boucle while ne s'exécute jamais → 0 décalage. C'est le comportement

O (n)

Conclusion : ces deux extrêmes illustrent la sensibilité du tri par insertion à l'ordre initial, contrairement à la sélection.

Exo 3Le bug du mauvais sensDifficile

Un élève écrit ce tri par insertion, mais il a inversé un signe dans la condition du while :

def tri_faux(t):
    n = len(t)
    for i in range(1, n):
        x = t[i]
        j = i - 1
        while j >= 0 and t[j] < x:   # < au lieu de >
            t[j + 1] = t[j]
            j = j - 1
        t[j + 1] = x
    return t

Que renvoie tri_faux([5, 2, 4, 1]) ? Expliquer pourquoi, et donner ce que fait ce code en général.

Voir la correction détaillée

Avec t[j] < x, on décale un élément vers la droite tant qu'il est plus petit que x. Autrement dit, on insère x avant tous les éléments plus petits que lui : les grands remontent vers la gauche.

Traçons [5, 2, 4, 1] :

i = 1

, x=2 ; t[0]=5 < 2 ? non → 2 reste en place → [5, 2, 4, 1].

i = 2

, x=4 ; t[1]=2 < 4 ? oui, on décale 2 ; t[0]=5 < 4 ? non → on pose 4 en case 1 → [5, 4, 2, 1].

i = 3

, x=1 ; aucun élément à gauche n'est < 1 → 1 reste en fin → [5, 4, 2, 1].

Résultat : [5, 4, 2, 1]. Le code trie en réalité par ordre décroissant. Ce n'est pas un plantage : c'est un tri correct… dans le mauvais sens. La leçon : le sens de la comparaison fixe le sens du tri.

Récap final — Ce qu'il faut absolument retenir

Deux tris quadratiques, en place, au programme de première année. La sélection est régulière ; l'insertion est opportuniste. Testez-vous.

Sais-tu écrire le tri par sélection et énoncer son invariant (« t[0..i-1] trié ET contient les $i$ plus petits ») ?
Sais-tu écrire le tri par insertion et énoncer son invariant (« t[0..i-1] trié ») ?
Sais-tu tracer chacun des deux tris à la main sur [5, 2, 4, 1] ?
Sais-tu que la sélection fait toujours $\frac{n ( n - 1 )}{2}$ comparaisons, indépendamment de l'ordre initial ?
Sais-tu que l'insertion est $O (n)$ au meilleur cas (liste triée) et $O (n^{2})$ au pire (triée à l'envers) ?
Sais-tu construire l'entrée qui déclenche le pire cas de l'insertion ?
Sais-tu ce que signifie « tri en place » et « tri stable », et lequel des deux tris est stable ?
Sais-tu pourquoi il faut sauvegarder $x = t [i]$ avant les décalages en insertion ?
Sais-tu citer le tri fusion $O (n lo g n)$ comme amélioration « diviser pour régner » ?

À savoir refaire

Démontrer que le tri par sélection effectue exactement $\frac{n ( n - 1 )}{2}$ comparaisons (somme $(n - 1) + (n - 2) + \dots + 1$ ).

Vue d'ensemble

Prérequis

Le cadre : trier une liste en place

Tri par sélection

Combien de comparaisons ?

Tri par insertion

Meilleur cas, pire cas : la différence clé

Comparer les deux tris

Ouverture : le tri fusion en O(n log n)

Exercices corrigés

Récap final — Ce qu'il faut absolument retenir

À savoir refaire

Débloque la fiche complète

Quiz — Tris

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?