C — Tris par insertion et par sélection — Fiche de révision MP2I Informatique

Vue d'ensemble

Trier un tableau, c'est réorganiser ses cases pour que les valeurs soient rangées dans l'ordre croissant. En MP2I, deux algorithmes fondateurs se font en manipulant directement les cases d'un int t[] : le tri par sélection et le tri par insertion. Tous deux sont quadratiques — leur coût grandit comme le carré de la taille — mais ils sont simples, se démontrent avec des invariants, et surtout ils obligent à maîtriser l'échange de deux cases en C, qui n'a rien d'automatique.

Au programme. Tri d'un tableau en place. Tri par sélection : recherche répétée du minimum du reste. Tri par insertion : insertion par décalages dans la partie triée. Invariants de boucle. Complexité dans le meilleur et le pire des cas. Échange de deux cases par variable temporaire.

Prérequis

c-tableaux-chaines — accéder à t[i], connaître la taille n, comprendre qu'un tableau se passe à une fonction sans sa taille.
c-premiers-pas — boucles for et while, condition if, déclaration de variables locales int.

🎯 Accompagnement Majorant

Les tris sont le premier vrai piège de l'info en prépa. Sur le papier ça paraît trivial, mais à l'écrit une borne de boucle fausse ou un échange sans variable temporaire coûte tous les points. Nos mentors alumni X · Centrale · Mines vous font écrire ces tris jusqu'à ce que les invariants deviennent un réflexe.

Trouver un mentor →

Deux notions à poser d'abord

Avant d'écrire une seule ligne de tri, deux définitions cadrent tout le chapitre. Elles expliquent où le tri travaille et comment on déplace concrètement une valeur en C.

Définition 1.1 — Tri en place

Un tri est dit en place s'il réorganise le tableau donné en n'utilisant qu'un nombre constant de variables auxiliaires, sans allouer un second tableau de taille $n$ . La mémoire supplémentaire est en $O (1)$ . Les tris par sélection et par insertion sont tous deux en place : ils déplacent les valeurs à l'intérieur du même int t[].

Définition 1.2 — Échange par variable temporaire

Échanger le contenu de deux cases t[i] et t[j] exige de mémoriser une des deux valeurs avant de l'écraser. En C, on utilise une variable intermédiaire :

int tmp = t[i];   // on sauvegarde t[i]
t[i] = t[j];      // on ecrase t[i] par t[j]
t[j] = tmp;       // on met la valeur sauvee dans t[j]

Il n'existe pas en C d'échange par affectation simultanée comme le t[i], t[j] = t[j], t[i] de Python. La variable temporaire est obligatoire.

🔍 Décryptage ligne par ligne

int tmp = t[i];On copie la valeur de t[i] dans tmp. Sans cette copie, la valeur serait perdue à la ligne suivante.

t[i] = t[j];On recopie t[j] dans t[i]. L'ancienne valeur de t[i] est maintenant écrasée, mais elle est en sûreté dans tmp.

t[j] = tmp;On place la valeur sauvegardée dans t[j]. L'échange est terminé : les deux cases ont bien permuté leur contenu.

On isole cet échange dans une petite fonction réutilisée par les deux tris :

void echanger(int t[], int i, int j) {
    int tmp = t[i];
    t[i] = t[j];
    t[j] = tmp;
}

🔍 Décryptage ligne par ligne

void echanger(int t[], int i, int j)Fonction sans valeur de retour (void). Elle reçoit le tableau t et deux indices. Comme un tableau est passé par son adresse, les modifications sur t sont visibles par l'appelant.

int tmp = t[i];Sauvegarde de t[i] avant écrasement.

t[i] = t[j]; t[j] = tmp;Les deux affectations qui finissent la permutation. Après l'appel, t[i] et t[j] sont échangées dans le tableau réel.

⚠ L'échange sans variable temporaire écrase une valeur. Si l'on écrit t[i] = t[j]; t[j] = t[i];, la première ligne détruit l'ancienne valeur de t[i]. La seconde recopie alors t[i] (déjà égal à t[j]) dans t[j] : les deux cases finissent égales à l'ancienne t[j]. Par exemple sur les valeurs 7 et 9, on obtient 9 et 9 au lieu de 9 et 7. La valeur 7 est perdue.

Tri par sélection

Idée : la partie gauche du tableau contient, à tout moment, les plus petites valeurs déjà rangées. À l'étape numéro i, on cherche l'indice du minimum du reste (les cases d'indice $i$ à $n - 1$ ), puis on l'échange avec la première case non triée, la case i. La zone triée gagne une case à chaque étape.

void tri_selection(int t[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int imin = i;
        for (int j = i + 1; j < n; j++) {
            if (t[j] < t[imin]) {
                imin = j;
            }
        }
        echanger(t, i, imin);
    }
}

🔍 Décryptage ligne par ligne

for (int i = 0; i < n - 1; i++)Boucle sur la position à remplir. On s'arrête à n-1 exclu : une fois les n-1 premières cases correctes, la dernière l'est forcément, inutile de la traiter.

int imin = i;On suppose provisoirement que le minimum du reste est en i. imin mémorise l'indice du plus petit trouvé, pas sa valeur.

for (int j = i + 1; j < n; j++)On parcourt toutes les cases après i pour chercher plus petit. On démarre à i+1 car la case i est déjà le candidat.

if (t[j] < t[imin]) imin = j;Si la case courante bat le minimum courant, on retient son indice. À la fin de la boucle interne, imin désigne le vrai minimum du reste.

echanger(t, i, imin);On place ce minimum en position i. Si imin == i l'échange ne change rien, ce qui est correct.

📝 Invariant de boucle. Juste avant l'itération d'indice i, les cases t[0..i-1] sont triées et contiennent les

i

plus petites valeurs du tableau. Elles ne bougeront plus jamais. C'est ce qui garantit qu'à la fin tout le tableau est trié.

Déroulons ce tri sur le tableau {5, 2, 4, 1}. À chaque étape on cherche le minimum de la zone non triée (à partir de l'indice i), puis on l'échange avec la case i.

Tri par sélection de {5, 2, 4, 1} — recherche du minimum puis échange
Étape (i)	Tableau avant	Min du reste (indice)	Échange	Tableau après
i = 0	5 2 4 1	1 (indice 3)	t[0] ↔ t[3]	1 2 4 5
i = 1	1 2 4 5	2 (indice 1)	t[1] ↔ t[1] (rien)	1 2 4 5
i = 2	1 2 4 5	4 (indice 2)	t[2] ↔ t[2] (rien)	1 2 4 5
Fin	Tableau trié			1 2 4 5 ✓

📝 Toujours quadratique. Le tri par sélection fait toujours le même travail, quel que soit le tableau : la boucle interne compare systématiquement toutes les cases du reste. Le nombre de comparaisons est

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

, soit

O (n^{2})

. Même sur un tableau déjà trié, il n'accélère pas.

Tri par insertion

C'est le tri du joueur de cartes : on prend les éléments un par un et on les insère à leur place dans la partie gauche déjà triée. Concrètement, pour placer la valeur courante x = t[i], on décale vers la droite toutes les cases de gauche plus grandes que x, ce qui creuse un trou où l'on dépose x.

void tri_insertion(int t[], int n) {
    for (int i = 1; i < n; i++) {
        int x = t[i];
        int j = i - 1;
        while (j >= 0 && t[j] > x) {
            t[j + 1] = t[j];
            j = j - 1;
        }
        t[j + 1] = x;
    }
}

🔍 Décryptage ligne par ligne

for (int i = 1; i < n; i++)On commence à i = 1 : une seule case (t[0]) est déjà triée toute seule, donc on insère à partir de la deuxième.

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

int j = i - 1;j pointe la dernière case de la zone triée, juste à gauche de x. On va remonter vers la gauche.

while (j >= 0 && t[j] > x)Tant qu'on n'a pas dépassé le bord gauche (j >= 0) ET que la case examinée est plus grande que x. L'ordre des deux tests compte : j >= 0 d'abord évite de lire t[-1].

t[j + 1] = t[j];On décale la valeur d'un cran vers la droite : elle laisse un trou à sa position.

j = j - 1;On recule d'une case pour examiner la valeur encore plus à gauche.

t[j + 1] = x;La boucle s'est arrêtée : j+1 est le trou final. On y dépose x. Attention, c'est j+1 et non j, car j a été décrémenté une fois de trop avant l'arrêt.

📝 Invariant de boucle. Juste avant l'itération d'indice i, les cases t[0..i-1] sont triées entre elles (mais ne sont pas nécessairement les plus petites : elles peuvent encore reculer quand on insère un petit élément plus tard). C'est la différence clé avec la sélection.

Déroulons l'insertion sur {5, 2, 4, 1}. La barre | sépare la zone triée (à gauche) de la zone à traiter.

Tri par insertion de {5, 2, 4, 1} — décalages puis dépôt de x
Étape (i)	x = t[i]	Décalages effectués	Tableau après dépôt
départ	—	—	5 \| 2 4 1
i = 1	2	5 vers la droite	2 5 \| 4 1
i = 2	4	5 vers la droite	2 4 5 \| 1
i = 3	1	5, 4, 2 vers la droite	1 2 4 5 ✓

📝 Meilleur cas linéaire, pire cas quadratique. Si le tableau est déjà trié, la condition t[j] > x est fausse d'emblée à chaque tour : aucun décalage, une seule comparaison par élément, coût

O (n)

. Si le tableau est trié à l'envers, chaque élément doit remonter jusqu'au début :

O (n^{2})

. Le tri par insertion s'adapte donc aux données presque triées, contrairement à la sélection.

🎯 Accompagnement Majorant

Pourquoi t[j+1] = x et pas t[j] = x ? Cette question revient chaque année et sépare ceux qui récitent le code de ceux qui le comprennent. Nos mentors alumni X · Centrale · Mines vous font tracer l'algorithme à la main jusqu'à ce que la position du trou soit une évidence, pas une formule mémorisée.

Trouver un mentor →

Comparer les deux tris

Les deux tris sont en place et de complexité au pire $O (n^{2})$ , mais ils ne se comportent pas de la même façon selon les données.

Récapitulatif des complexités
Critère	Tri par sélection	Tri par insertion
Comparaisons (toujours)	$\frac{n ( n - 1 )}{2}$	de $n - 1$ à $\frac{n ( n - 1 )}{2}$
Meilleur cas (tableau trié)	$O (n^{2})$	$O (n)$
Pire cas (tableau à l'envers)	$O (n^{2})$	$O (n^{2})$
Nombre d'échanges / déplacements	au plus $n - 1$ échanges	jusqu'à $O (n^{2})$ décalages
Mémoire supplémentaire	$O (1)$	$O (1)$

💡 Un cas où l'insertion écrase la sélection. Sur un tableau presque trié (quelques éléments à leur place près), l'insertion fait très peu de décalages et tourne quasiment en

O (n)

. La sélection, elle, refait aveuglément ses

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

comparaisons. À l'inverse, la sélection minimise le nombre d'écritures dans le tableau : utile si écrire coûte cher.

📐 Méthode — Dérouler un tri à la main sans se tromper

Écris le tableau et repère la frontière zone triée / zone à traiter (indice i).
Pour la sélection : balaie tout le reste, note l'indice du minimum, puis échange avec la case i (une seule écriture double).
Pour l'insertion : mets x = t[i] de côté, puis décale vers la droite chaque case de gauche strictement plus grande que x, une par une, jusqu'à trouver la place, et dépose x.
Recopie le tableau complet après chaque étape i : ne jamais garder l'état en tête.

Exercices corrigés

Exo 1Une passe de sélectionFacile

On applique le tri par sélection au tableau {4, 3, 1, 2}. Donne l'état du tableau juste après la première itération (i = 0). Indique aussi l'indice du minimum trouvé.

Voir la correction détaillée

On cherche le minimum de tout le tableau (indices 0 à 3). Les valeurs sont 4, 3, 1, 2 : le minimum est 1, situé à l'indice 2. Donc imin = 2.

On échange t[0] et t[2] : les valeurs 4 et 1 permutent.

Résultat après i = 0 : {1, 3, 4, 2}. La case 0 contient désormais la plus petite valeur ; elle ne bougera plus.

Exo 2Insertion pas à pas et comptageIntermédiaire

On trie {3, 1, 4, 2} par insertion. Donne l'état du tableau après chaque valeur de i (i = 1, 2, 3), puis le nombre total de décalages (affectations t[j+1] = t[j]) effectués sur tout le tri.

Voir la correction détaillée

i = 1, x = 1 : on compare à t[0] = 3 > 1, on décale 3 vers la droite (1 décalage), puis j = -1 stoppe. On dépose 1 en case 0. Tableau : {1, 3, 4, 2}.

i = 2, x = 4 : on compare à t[1] = 3 > 4 ? Non. Aucun décalage. On redépose 4 à sa place. Tableau inchangé : {1, 3, 4, 2}.

i = 3, x = 2 : t[2] = 4 > 2 vrai, on décale 4 (1). t[1] = 3 > 2 vrai, on décale 3 (2). t[0] = 1 > 2 ? Non, stop. On dépose 2 en case 1. Tableau : {1, 2, 3, 4}.

Décalages : 1 (i=1) + 0 (i=2) + 2 (i=3) = 3 décalages au total.

Exo 3Tri décroissant et détection de bugDifficile

1. Modifie le tri par sélection pour qu'il trie en ordre décroissant (plus grand en premier). 2. Un élève écrit l'échange ainsi, sans variable temporaire : t[i] = t[imin]; t[imin] = t[i];. Explique précisément ce qui se passe sur {5, 2, 4, 1} à la première étape.

Voir la correction détaillée

1. Tri décroissant. Il suffit de chercher le maximum du reste au lieu du minimum : on remplace la comparaison t[j] < t[imin] par t[j] > t[imax] (en renommant imin en imax). Le reste du code est identique.

void tri_selection_decroissant(int t[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int imax = i;
        for (int j = i + 1; j < n; j++) {
            if (t[j] > t[imax]) {
                imax = j;
            }
        }
        echanger(t, i, imax);
    }
}

2. Bug de l'échange. À la première étape, i = 0, le minimum est 1 à l'indice 3, donc imin = 3. La ligne t[0] = t[3]; écrase la valeur 5 par 1 : le tableau devient {1, 2, 4, 1}. Puis t[3] = t[0]; recopie t[0] (déjà égal à 1) dans t[3] : toujours {1, 2, 4, 1}. La valeur 5 a disparu, remplacée par un doublon de 1. Le tableau final ne sera pas une permutation de l'original : le tri est cassé. C'est exactement le rôle de la variable temporaire d'éviter cette perte.

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

Ces deux tris quadratiques sont la base de tout le cours d'algorithmique. Vérifie que chaque point ci-dessous est un réflexe, pas une vague intuition.

Sais-tu échanger deux cases t[i] et t[j] en C avec une variable tmp, et expliquer pourquoi elle est obligatoire ?
Sais-tu qu'un tri en place n'utilise qu'une mémoire supplémentaire en $O (1)$ , sans second tableau ?
Sais-tu écrire le tri par sélection : recherche de l'indice du minimum du reste, puis un seul échange par étape ?
Sais-tu écrire le tri par insertion par décalages, et justifier le t[j+1] = x final (et non t[j]) ?
Sais-tu que la sélection fait toujours $\frac{n ( n - 1 )}{2}$ comparaisons, donc $O (n^{2})$ même sur un tableau déjà trié ?
Sais-tu que l'insertion est en $O (n)$ au meilleur cas (tableau trié) et $O (n^{2})$ au pire (tableau à l'envers) ?
Sais-tu énoncer l'invariant de chaque tri, et expliquer pourquoi celui de l'insertion n'affirme pas les plus petites valeurs ?
Sais-tu repérer le bug d'un échange sans tmp et prédire les doublons qu'il crée ?
Sais-tu justifier les bornes i < n - 1 (sélection) et j >= 0 (insertion) ?

C — Tris par insertion et par sélection

Vue d'ensemble

Prérequis

Deux notions à poser d'abord

Tri par sélection

Tri par insertion

Comparer les deux tris

Exercices corrigés

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

Débloque la fiche complète

Quiz — C : tris

Fiches associées

C — Premiers pas

C — Pointeurs et allocation dynamique

OCaml — Premiers pas

OCaml — Filtrage et listes

C — Structures et listes chaînées

C — Piles et files

Tu veux aller plus loin sur ce chapitre ?