Les tris
Ce que ce chapitre apporte
- 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.
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, le plus rapide des trois en demande 29 et le plus lent 223. 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.
Trier, c'est ranger une suite de valeurs dans l'ordre. 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. La figure de ce module s'arrête au-delà de 500 pas, et le tri fusion est gourmand : 223 pas sur ces six valeurs, 329 sur huit, 445 sur dix, et sur douze il franchit le plafond 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.
Les nombres de pas relevés ici comptent le travail du traceur, pas des secondes. Ils servent à comparer des algorithmes entre eux sur les mêmes données, ce qui est exactement ce qu'on demande à une mesure de coût. La notation qui permet d'exprimer ce coût indépendamment de la machine, les classes usuelles et la distinction entre cas moyen et pire cas sont traitées dans le chapitre consacré à la complexité, et rien n'en est redit ici.
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
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.
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
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 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. Écrite dans l'autre sens, la condition demanderait t[0], qui n'existe pas dans ce cours et interrompt le déroulement. 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, un coût qui croît comme le carré du nombre de valeurs. 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é.
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.
| 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 |
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 coût ne dépend que du nombre de valeurs. Sur des données presque triées, qui sont le cas le plus courant en pratique, l'écart mesuré atteint déjà un facteur deux sur six valeurs.
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 11 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
Fusionner
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
223 pas, et une pile qui monte jusqu'à cinq cadres. La commande « suivant » vaut la peine ici : la pile affichée 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.
Sur les mêmes données déjà triées qui faisaient tomber le tri par insertion à 29 pas, le tri fusion en demande 219, soit quatre de moins que sur le désordre. Il ne s'adapte à rien : il découpe et fusionne exactement de la même façon, quoi qu'on lui donne.
| Tri | Désordre | Déjà trié |
|---|---|---|
| Sélection | 71 pas | 64 pas |
| Insertion | 59 pas | 29 pas |
| Fusion | 223 pas | 219 pas |
Lire ce tableau comme un classement serait une faute de raisonnement. Sur six valeurs, le tri fusion est nettement le plus coûteux, et c'est normal : il paie des appels de fonction et des recopies de tranches que les deux autres n'ont pas. Son avantage n'apparaît que lorsque le nombre de valeurs grandit, là où le coût des deux premiers croît comme le carré tandis que le sien croît beaucoup plus lentement. Le plafond de 500 pas interdit de le montrer ici ; la courbe des classes de coût, elle, est dans le chapitre consacré à la complexité.
La stabilité, ou ce qui arrive aux valeurs égales
Un tri est stable quand deux valeurs égales sortent dans l'ordre où elles étaient entrées. 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.
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 en arrière, à 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.
Vérification
1.Sur [1, 2, 3, 5, 7, 9], le tri par insertion demande 29 pas et le tri par sélection 64. Pourquoi cet écart ?
2.Dans le tri par sélection, que contient la variable m ?
3.Pourquoi la fusion compare-t-elle avec g[i] <= d[j] plutôt qu'avec g[i] < d[j] ?
4.Le tri fusion demande 223 pas sur six valeurs en désordre et 219 sur les mêmes valeurs déjà triées. Qu'en conclure ?
5.Trier des dossiers par priorité avec un tri non stable produit quoi ?
La méthode
- Nommer le travail avant d'écrire la boucle. Chercher un minimum et décaler une portion sont deux gestes différents, et le tri qu'on écrit est celui des deux qu'on a en tête.
- Mettre la valeur de côté avant tout déplacement. Un échange sans variable de garde et un décalage sans copie préalable perdent une valeur, silencieusement.
- Tester la validité d'un indice avant son contenu.
j >= 1 ET t[j] > vse déroule ; l'ordre inverse s'arrête. - Dérouler sur des données déjà triées autant que sur du désordre : c'est le jeu d'essai qui révèle si l'algorithme s'adapte ou non.
- Relever le compteur de pas plutôt que d'estimer. Deux tris d'apparence jumelle affichent 64 et 29 sur les mêmes valeurs.
- Vérifier la stabilité sur des clés égales dès que la valeur triée est attachée à autre chose qu'elle-même.
Synthèse
- Les trois tris rendent le même résultat sur les mêmes données et coûtent respectivement 71, 59 et 223 pas : le résultat ne dit rien du travail fourni.
- Le tri par sélection cherche et échange peu ; le tri par insertion déplace et s'arrête tôt. C'est ce qui les sépare, pas leur forme.
- La fusion de deux suites triées est une opération autonome, et le tri fusion n'est que son emploi récursif après une découpe en deux.
- Le tri par insertion est stable et adaptatif, le tri par sélection n'est ni l'un ni l'autre, le tri fusion est stable et insensible à l'ordre de départ.
- Le choix d'un tri se fait sur la forme attendue des données, et se vérifie au compteur de pas.
Le chapitre suivant quitte le tableau rangé côte à côte pour deux disciplines d'accès qui décident, non plus de l'ordre des valeurs, mais de celle qui sort la première : piles et files.