Les algorithmes de tri
Ce que ce chapitre apporte 5 points
- Dérouler le tri par sélection, le tri par insertion et le tri fusion sur un même jeu de données.
- Distinguer les deux tris quadratiques par ce qu'ils font réellement, chercher ou déplacer.
- Écrire la fusion de deux suites déjà triées, puis le tri récursif qui s'appuie dessus.
- Reconnaître un tri stable et repérer les situations où la stabilité change le résultat.
- Choisir un tri en fonction de la forme des données plutôt que par habitude.
Un service de maintenance reçoit chaque nuit le relevé horodaté de ses capteurs, dix mille mesures rangées à quelques retards près. Il doit aussi classer une fois pour toutes un référentiel de mille pièces arrivé en vrac, pour y chercher ensuite par dichotomie. Le même tri convient-il aux deux ?
Trier paraît une évidence, jusqu'au moment où il faut l'écrire. Trois algorithmes suffisent à couvrir l'essentiel, et ils ne se valent pas : sur les mêmes six valeurs en désordre, le plus économe en demande 59 pas et le plus gourmand 245. Ce chapitre les déroule côte à côte et relève chaque fois le compteur de pas, parce qu'un tri ne se choisit pas au ressenti. Il s'appuie sur les indices des tableaux, sur la pile des appels de la récursivité, et sur la fonction Tranche et le découpage en deux de diviser pour régner.
Trier, c'est ranger une suite de valeurs dans l'ordre. Le chapitre précédent en a donné la raison la plus courante : un relevé trié se fouille par dichotomie, et le tri, payé une fois, rend rapides toutes les recherches qui suivent. Le résultat est le même quel que soit l'algorithme employé, et c'est précisément ce qui rend la comparaison intéressante : la seule chose qui change est le travail fourni pour y arriver. Le compteur de pas de la figure rend ce travail visible, et il permet de trancher des questions qui, autrement, resteraient des opinions.
Un jeu d'essai de six valeurs, et pourquoi six
Tous les algorithmes de ce chapitre partent du même tableau :
| Indice | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Valeur | 7 | 3 | 9 | 1 | 5 | 2 |
Six valeurs, et pas davantage. Le déroulement du pseudo-code s'arrête au-delà de 500 pas, et le tri fusion est gourmand : 245 pas sur ces six valeurs, 358 en y ajoutant 8 et 4, 479 en ajoutant encore 10 et 6, et dès onze valeurs il franchit le plafond, quel que soit leur ordre, et s'interrompt sans avoir rien trié. Six est donc la taille qui laisse dérouler les trois tris jusqu'au bout tout en gardant une marge confortable.
Le compteur de pas des algorithmes compte les lignes exécutées, selon les règles posées au chapitre sur la récursivité : en-têtes de boucle, tests et mises à jour d'indices compris. Les figures animées de ce chapitre, elles, comptent des gestes sur les valeurs : une comparaison, ou un déplacement. Un décalage de l'insertion vaut ainsi deux gestes, une comparaison et un déplacement, mais trois lignes ; un tour de recherche de la sélection vaut un seul geste, mais deux lignes, et trois quand le minimum provisoire change ; et le tri fusion paie en plus, à chaque découpe, des appels et des recopies que la figure animée ne compte pas. Les deux mesures s'accordent sur les données déjà rangées. Sur le désordre, elles se contredisent : la sélection fait moins de gestes, vingt contre vingt-huit, et l'insertion moins de pas, 59 contre 71. Aucune n'a tort : un coût se compare avec une seule mesure à la fois, en disant laquelle. Aucune ne compte des secondes non plus, et la notation qui exprime un coût indépendamment de la machine est traitée dans le chapitre consacré à la complexité.
Le tri par sélection : chercher, puis échanger
Le principe tient en une phrase : chercher la plus petite valeur restante, et la mettre à sa place définitive par un échange.
programme principal
comparéesdéplacéesordonnées entre ellesà leur place définitive
Revenir ensuite au pas à pas, avec « Un geste », pour voir ce que fait la boucle intérieure : elle compare cinq fois, puis quatre, puis trois. C'est ce rythme décroissant qui donne les quinze comparaisons affichées à la fin.
Le déroulement demande 71 pas et affiche [1, 2, 3, 5, 7, 9]. En suivant la figure pas à pas, deux choses se voient bien. D'abord la variable m : elle ne retient pas le minimum, mais l'indice du minimum, ce qui permet l'échange ensuite. Ensuite le rythme : la boucle intérieure tourne cinq fois, puis quatre, puis trois, et ainsi de suite, tandis que l'échange, lui, n'a lieu qu'une fois par tour de la boucle extérieure.
Le tri par sélection fait donc beaucoup de comparaisons et très peu de déplacements : cinq échanges au total, quoi qu'il arrive.
Écrire l'échange en deux lignes, t[i] ← t[m] puis t[m] ← t[i]. La première ligne a déjà écrasé l'ancienne valeur de t[i], et la seconde la recopie sur elle-même : les deux cases finissent identiques et une valeur disparaît du tableau. La variable garde n'est pas une commodité, elle est indispensable.
Dans le tri par sélection, que contient la variable m ?
Le tri par insertion : ouvrir une place et décaler
Le tri par insertion procède comme une main de cartes qu'on remet en ordre : chaque nouvelle valeur est glissée à sa place parmi celles déjà rangées, en repoussant d'un cran celles qui lui sont supérieures.
programme principal
comparéesdéplacéesordonnées entre ellesà leur place définitive
Relancer ensuite en suivant les barres rouges. Chaque décalage en fait rougir une ; le 1 en provoque trois à lui seul, et le 2, parti du fond, quatre. Les compteurs le disent d'ailleurs à la fin : moins de comparaisons que la sélection, et bien plus de déplacements.
59 pas, et le même résultat. La valeur à placer est mise de côté dans v avant que le décalage ne commence : sans cette copie, le premier décalage l'écraserait. La condition j >= 1 ET t[j] > v s'arrête dès qu'une valeur plus petite ou égale est rencontrée, et c'est cet arrêt anticipé qui fait toute la différence avec le tri précédent.
L'ordre des deux tests dans j >= 1 ET t[j] > v n'est pas indifférent, et la raison tient à la façon dont se lit un ET : de gauche à droite, en s'arrêtant dès que le résultat est connu. Quand j vaut 0, j >= 1 est faux, la condition entière l'est donc aussi, et t[j] n'est jamais demandé. Écrite dans l'autre sens, la condition commencerait par demander t[0], qui n'existe pas dans ce cours, et le déroulement s'interromprait. Python lit ses and de la même façon. Tester d'abord que l'indice est valide, ensuite ce qu'il contient : c'est une habitude à prendre bien au-delà des tris.
Ce qui les sépare vraiment
Les deux tris précédents se ressemblent : deux boucles imbriquées, et un coût qui croît comme le carré du nombre de valeurs. Ce coût se compte sans rien dérouler. Sur six valeurs, la sélection compare cinq fois au premier tour, puis quatre, trois, deux et une : 5 + 4 + 3 + 2 + 1 = 15 comparaisons. Sur cent valeurs, la même somme vaut 4 950, et sur mille, 499 500 : à peu près la moitié du carré du nombre de valeurs, ce qu'on appelle un coût quadratique. Dix fois plus de valeurs demandent cent fois plus de comparaisons. L'insertion en fait autant dans le pire des cas, un tableau rangé à l'envers, où chaque valeur recule jusqu'au début, et à peu près la moitié sur des valeurs tirées au hasard : son coût reste quadratique.
Pourtant ils ne font pas le même travail. Le tri par sélection cherche : il balaie systématiquement tout ce qui reste, même quand la réponse est déjà sous ses yeux. Le tri par insertion déplace : il ne regarde que ce qui le gêne, et s'arrête dès qu'il ne gêne plus.
Le jeu d'essai qui sépare les deux est celui qui est déjà trié. Les voici côte à côte, lancés ensemble sur les mêmes valeurs, un geste chacun par battement.
comparéesdéplacéesordonnées entre ellesà leur place définitiveUn geste chacun par battement : la piste qui s'arrête la première en a fait moins.
Comparer ensuite les compteurs des deux premières figures, celles du désordre : la sélection y fait vingt gestes et l'insertion vingt-huit, l'insertion payant ses décalages. C'est tout l'objet de la section : deux algorithmes du même ordre de grandeur peuvent se comporter à l'opposé selon l'entrée.
programme principal
29 pas, contre 59 sur les données en désordre. La boucle TantQue échoue à son premier test à chaque tour, aucun décalage n'a lieu, et le tri se réduit à un simple parcours de vérification.
programme principal
64 pas, contre 71. Le tri par sélection ne s'aperçoit de rien : il refait les quinze mêmes comparaisons et les cinq mêmes échanges, dont chacun échange une case avec elle-même. Les sept pas d'écart viennent de la seule ligne m ← j : sur le désordre, un nouveau minimum provisoire apparaît sept fois pendant les recherches, deux fois au premier tour, une au deuxième, trois au troisième et une au quatrième ; sur des valeurs rangées, jamais.
| Jeu de données | Sélection | Insertion |
|---|---|---|
[7, 3, 9, 1, 5, 2] | 71 pas | 59 pas |
[1, 2, 3, 5, 7, 9] | 64 pas | 29 pas |
L'un s'adapte aux données, l'autre les ignore. Le tri par insertion est adaptatif : il coûte d'autant moins que les données sont déjà en ordre. Le tri par sélection ne l'est pas : son nombre de comparaisons et d'échanges ne dépend que du nombre de valeurs. Sur des données déjà rangées, et presque autant sur des données presque rangées, comme un relevé horodaté où quelques mesures arrivent en retard, l'écart atteint un facteur deux dès six valeurs : une seule paire de voisines inversée laisse encore 32 pas à l'insertion et 65 à la sélection.
Sur [1, 2, 3, 5, 7, 9], le tri par insertion demande 29 pas et le tri par sélection 64. Pourquoi cet écart ?
Fusionner deux suites déjà triées
Le troisième tri repose sur une opération autonome, qui mérite d'être écrite et déroulée seule : assembler deux suites déjà triées en une seule qui l'est aussi. Il suffit de comparer les deux têtes et de prendre la plus petite.
Il faut d'abord de quoi découper un tableau. La fonction Tranche extrait une portion entre deux indices, comme au chapitre sur diviser pour régner :
programme principal
La figure affiche [3, 9, 1] en 12 pas. Le décalage k - a + 1 est le seul point délicat : la case a du tableau d'origine devient la case 1 de la tranche.
La fusion elle-même avance avec trois indices, un dans chaque suite et un dans le résultat :
programme principal
aucune variable
41 pas pour produire [1, 2, 3, 5, 7, 9]. Les deux boucles finales ne sont pas une précaution inutile : la première suite épuisée laisse toujours un reste dans l'autre, et ce reste est déjà trié, il n'y a qu'à le recopier.
Le test s'écrit g[i] <= d[j] et non g[i] < d[j]. À valeurs égales, celle de la suite de gauche passe d'abord. Cette préférence paraît arbitraire ; la section sur la stabilité montre qu'elle ne l'est pas.
Le tri fusion : couper, trier, fusionner
Tout est en place. Un tableau d'une seule case est déjà trié, c'est le cas de base. Sinon, il se coupe en deux moitiés, chacune se trie de la même façon, et les deux résultats se fusionnent.
programme principal
245 pas, et une pile qui monte jusqu'à cinq cadres. La commande « suivant » vaut la peine ici : la rangée des cadres, sous l'algorithme, montre les découpes descendre jusqu'aux tableaux d'une seule case, puis les fusions remonter deux par deux. Le tri ne se fait pas à la descente, il se fait au retour.
Le même tri se regarde mieux animé. La figure suivante ne montre plus les lignes exécutées, mais les valeurs qui bougent : neuf comparaisons et seize déplacements, chaque déplacement étant une valeur recopiée à sa place dans le morceau qu'on fusionne.
comparéesdéplacéesordonnées entre ellesà leur place définitive
Sur les mêmes données déjà triées qui faisaient tomber le tri par insertion à 29 pas, le tri fusion en demande 238, soit sept de moins que sur le désordre. Il ne s'adapte presque à rien : il découpe et fusionne de la même façon quoi qu'on lui donne. Les sept pas qu'il gagne viennent de ce que, sur des valeurs rangées, chaque fusion épuise d'abord sa moitié gauche : deux comparaisons de moins, sept au lieu de neuf, et le reste de la moitié droite recopié tel quel par la dernière boucle.
| Tri | Désordre | Déjà trié |
|---|---|---|
| Sélection | 71 pas | 64 pas |
| Insertion | 59 pas | 29 pas |
| Fusion | 245 pas | 238 pas |
Lire ce tableau comme un classement serait une faute de raisonnement. Sur six valeurs, le tri fusion est nettement le plus coûteux au compteur de pas, et c'est normal : il paie des appels de fonction et des recopies de tranches que les deux autres n'ont pas. Son avantage tient à une autre façon de grandir. Les deux premiers ont un coût quadratique : près d'un demi-million de comparaisons pour la sélection sur mille valeurs. La fusion, elle, travaille par étages. À chaque étage de découpe, les fusions réunies passent chaque valeur une fois, et il y a autant d'étages que de divisions par deux : trois pour huit valeurs, dix pour mille, comme au chapitre précédent. Mille valeurs lui coûtent donc au plus dix mille comparaisons, dix étages de mille valeurs, et en pratique moins de neuf mille, quand la sélection en demande 499 500. Le nom de ces deux façons de grandir, et leurs courbes, sont donnés dans le chapitre consacré à la complexité.
Le compteur de pas du pseudo-code s'arrête trop tôt pour le montrer, puisque le tri fusion y franchit le plafond dès onze valeurs. La figure animée, elle, compte des gestes et n'a pas ce plafond : voici la fusion et l'insertion sur trente-deux valeurs.
comparéesdéplacéesordonnées entre ellesà leur place définitiveUn geste chacun par battement : la piste qui s'arrête la première en a fait moins.
Le tri fusion demande 245 pas sur six valeurs en désordre et 238 sur les mêmes valeurs déjà triées. Qu'en conclure ?
La stabilité, ou ce qui arrive aux valeurs égales
Que deviennent deux valeurs égales ? Tant que les données se résument à des nombres, la question n'a aucun intérêt : deux 7 sont interchangeables. Elle devient décisive dès que la valeur triée n'est qu'une clé attachée à autre chose : une priorité attachée à un dossier, une date attachée à une mesure.
Un tri est stable si, pour deux éléments de même clé, l'ordre de départ est conservé dans le résultat. Cette propriété permet de trier en plusieurs passes : trier d'abord par date, puis par client, donne des groupes par client dont chacun reste trié par date.
Faute d'enregistrements dans le moteur, la clé et l'étiquette se tiennent dans deux tableaux parallèles, à la même position. Quatre dossiers, deux niveaux de priorité :
| Position | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Clé | 2 | 1 | 2 | 1 |
| Étiquette | A | B | C | D |
Un tri stable doit rendre B, D, A, C : les deux clés 1 dans leur ordre d'arrivée, puis les deux clés 2 dans le leur.
programme principal
Le tri par sélection rend ["B", "D", "C", "A"] en 46 pas. Les clés sont bien triées, mais A est passée derrière C alors qu'elle la précédait. La responsable est visible dans la trace : l'échange projette la valeur de la case i loin vers la fin du tableau, à la place du minimum, sans se soucier de ce qui vivait entre les deux.
programme principal
Le tri par insertion rend ["B", "D", "A", "C"] en 38 pas, l'ordre attendu. La condition cle[j] > vc est stricte : le décalage s'arrête devant une clé égale, et la nouvelle valeur se pose derrière elle. Le tri fusion est stable pour la même raison, le <= de la fusion : à valeurs égales, celle de la moitié gauche, arrivée la première, sort d'abord.
1.Pourquoi la fusion compare-t-elle avec g[i] <= d[j] plutôt qu'avec g[i] < d[j] ?
2.Trier des dossiers par priorité avec un tri non stable peut produire quoi ?
Mettre en pratique
Le coût d'un tri se compte avant de se mesurer : la forme des boucles et celle des données suffisent, sans dérouler une seule ligne.
Compter les comparaisons avant de dérouler
- 1.
Combien de comparaisons le tri par sélection fait-il sur un lot de 50 valeurs ?
- 2.
Combien d'échanges fait-il sur ces 50 valeurs ?
- 3.
Un relevé passe de 1 000 à 4 000 valeurs. Par combien le nombre de comparaisons du tri par sélection est-il multiplié ?
- 4.
Combien de comparaisons le tri par insertion fait-il sur un relevé de 10 000 mesures déjà rangées ?
- 5.
Et sur 2 000 mesures rangées à l'envers ?
- 6.
Combien d'étages de découpe le tri fusion traverse-t-il sur 5 000 valeurs, du tableau entier jusqu'aux tableaux d'une seule case ?
- 7.
Avec au plus une comparaison par valeur et par étage, combien de comparaisons le tri fusion fait-il au plus sur ces 5 000 valeurs ?
Dérouler à la main le tri par sélection sur [4, 1, 3, 2] : donner, pour chaque tour, l'indice du minimum trouvé et le tableau après l'échange, puis compter les comparaisons et les échanges.
| Tour | Cases parcourues | Indice du minimum | Tableau après l'échange |
|---|---|---|---|
| 1 | 1 à 4 | 2, la valeur 1 | [1, 4, 3, 2] |
| 2 | 2 à 4 | 4, la valeur 2 | [1, 2, 3, 4] |
| 3 | 3 à 4 | 3, la valeur 3 | [1, 2, 3, 4] |
Le premier tour compare trois fois, le deuxième deux fois, le troisième une fois : 3 + 2 + 1 = 6 comparaisons, et trois échanges, un par tour. Le tableau est rangé dès le deuxième tour, mais la sélection ne s'en aperçoit pas : le troisième tour cherche encore, et échange la case 3 avec elle-même. La figure animée donne les mêmes comptes, six comparaisons et trois déplacements :
comparéesdéplacéesordonnées entre ellesà leur place définitive
Choisir un tri pour chacune des trois situations suivantes, et justifier le choix. Un relevé horodaté de dix mille mesures, rangé à quelques mesures près, arrivées en retard. Mille références de pièces en vrac, à trier une fois pour y chercher ensuite des milliers de fois par dichotomie. Des dossiers déjà classés par date, à regrouper par client sans perdre l'ordre des dates à l'intérieur de chaque groupe.
Le relevé presque rangé : l'insertion. Elle est adaptative : chaque mesure ne recule que de quelques cases, et le coût reste proche d'un simple parcours. La sélection, qui ignore l'ordre existant, ferait ses 49 995 000 comparaisons, à peu près la moitié du carré de dix mille, pour ne presque rien déplacer.
Les mille références en vrac : le tri fusion. Sur des données en désordre, il ne dépasse pas neuf mille comparaisons, là où la sélection en fait 499 500 et l'insertion, en moyenne, autour d'un quart de million. Le tri se paie une fois ; chaque recherche par dichotomie coûte ensuite une dizaine d'examens.
Les dossiers à regrouper par client : un tri stable, l'insertion ou la fusion. Trier par client avec un tri stable garde, à client égal, l'ordre de départ, c'est-à-dire l'ordre des dates. La sélection, qui n'est pas stable, pourrait mélanger les dates d'un même client.
Chapitre révisé en octobre 2026 · Une erreur dans ce chapitre ?
Dans la bibliothèque d'exercices
Chercher le plus petit et l'échanger, insérer une valeur à sa place, et fusionner deux moitiés triées.
- Trier cinq valeurs par sélection4 · Analyser
- La fusion qui oublie le reste4 · Analyser
- Trouver la place d'une valeur4 · Analyser