Les algorithmes de tri

Comprendre ce qu’est un tri

Un algorithme de tri réorganise une collection de valeurs selon un ordre donné. En NSI, on trie souvent une liste de nombres dans l’ordre croissant, mais le principe reste le même pour des mots, des dates ou des objets plus complexes. Il faut seulement définir une règle de comparaison.

Une liste est triée dans l’ordre croissant si chaque élément est inférieur ou égal à celui qui le suit. Par exemple, [2, 4, 4, 7, 9] est triée. La liste [2, 7, 4, 9] ne l’est pas, car 7 est placé avant 4.

Un algorithme de tri doit être précis. Il ne suffit pas de dire : « on met les nombres dans l’ordre ». Il faut expliquer quelles cases on compare, quand on échange deux valeurs, quand on s’arrête, et pourquoi le résultat final est bien trié.

Trois idées reviennent souvent :

• Comparer deux éléments pour savoir lequel doit apparaître avant l’autre.
• Échanger deux éléments quand ils ne sont pas au bon endroit.
• Parcourir la liste avec un ou plusieurs indices.

On distingue aussi deux propriétés utiles.

• Un tri est en place s’il modifie directement la liste sans construire une grande nouvelle liste.
• Un tri est stable s’il conserve l’ordre relatif des éléments égaux.

Ces propriétés ne remplacent pas la correction de l’algorithme. Elles servent à comparer plusieurs méthodes quand elles donnent toutes une liste triée.

Le tri par sélection

Le tri par sélection repose sur une idée simple : à chaque étape, on cherche le plus petit élément dans la partie non triée, puis on le place au début de cette partie.

La liste se découpe donc en deux zones. À gauche, la zone déjà triée. À droite, la zone pas encore triée. Au départ, la zone triée est vide. À chaque passage, elle grandit d’un élément.

Principe

1. On part de la première position.
2. On cherche le minimum dans toute la partie restante de la liste.
3. On échange ce minimum avec l’élément placé à la position courante.
4. On avance d’une position.
5. On recommence jusqu’à ce que toute la liste soit triée.

Un pseudo-code possible est :

pour i allant de 0 à n - 2

indice_min prend la valeur i

pour j allant de i + 1 à n - 1

si liste[j] est plus petit que liste[indice_min]

indice_min prend la valeur j

échanger liste[i] et liste[indice_min]

Exemple pas à pas

On trie la liste [7, 3, 9, 1, 5] dans l’ordre croissant.

1. Position 0. On cherche le minimum dans [7, 3, 9, 1, 5]. C’est 1. On échange 7 et 1. Liste obtenue : [1, 3, 9, 7, 5].
2. Position 1. La partie triée est [1]. On cherche le minimum dans [3, 9, 7, 5]. C’est 3. Il est déjà à la bonne place. Liste inchangée : [1, 3, 9, 7, 5].
3. Position 2. La partie triée est [1, 3]. On cherche le minimum dans [9, 7, 5]. C’est 5. On échange 9 et 5. Liste obtenue : [1, 3, 5, 7, 9].
4. Position 3. On cherche le minimum dans [7, 9]. C’est 7. Il est déjà à la bonne place. Liste finale : [1, 3, 5, 7, 9].

Le tri par sélection est facile à justifier. Après chaque passage, la partie gauche contient les plus petits éléments de la liste, dans le bon ordre. Cette idée sert d’invariant : elle reste vraie du début à la fin.

Le tri par insertion

Le tri par insertion fonctionne comme un rangement progressif. On considère que le début de la liste est déjà trié. On prend ensuite le premier élément non trié et on l’insère à sa bonne place dans la partie gauche.

Cette méthode ressemble au rangement de cartes dans une main. On garde les cartes déjà rangées, puis on place chaque nouvelle carte au bon endroit.

Principe

1. On commence au deuxième élément de la liste.
2. On mémorise cet élément dans une variable.
3. On décale vers la droite les éléments plus grands que lui dans la partie déjà triée.
4. On place l’élément mémorisé dans la case libérée.
5. On passe à l’élément suivant.

Un pseudo-code possible est :

pour i allant de 1 à n - 1

valeur prend la valeur liste[i]

j prend la valeur i - 1

tant que j est positif ou nul et liste[j] est plus grand que valeur

liste[j + 1] prend la valeur liste[j]

j diminue de 1

liste[j + 1] prend la valeur valeur

Exemple pas à pas

On trie la liste [6, 2, 8, 4].

1. On regarde 2. La partie gauche [6] est triée. Comme 6 est plus grand que 2, on décale 6 vers la droite. On place 2 au début. Liste : [2, 6, 8, 4].
2. On regarde 8. La partie gauche [2, 6] est triée. 8 est plus grand que 6, il reste en place. Liste : [2, 6, 8, 4].
3. On regarde 4. La partie gauche [2, 6, 8] est triée. 8 est plus grand que 4, on le décale. 6 est plus grand que 4, on le décale aussi. 2 est plus petit que 4, on s’arrête. On place 4 après 2. Liste : [2, 4, 6, 8].

Le tri par insertion est souvent efficace quand la liste est déjà presque triée. Dans ce cas, il y a peu de décalages à effectuer.

Comparer les algorithmes de tri

Pour comparer des tris, on ne regarde pas seulement le résultat. Tous les tris corrects doivent produire une liste ordonnée. On observe surtout le nombre de comparaisons, le nombre d’échanges ou de décalages, et la mémoire utilisée.

En NSI, on décrit souvent le coût d’un algorithme selon la taille de l’entrée. Si une liste contient beaucoup d’éléments, un tri trop coûteux devient lent. On utilise alors des ordres de grandeur, comme un coût linéaire, quadratique ou quasi linéaire.

Algorithme	Idée principale	Comportement général	Remarque utile
Tri par sélection	Chercher le minimum restant	Beaucoup de comparaisons, même si la liste est presque triée	Simple à comprendre et à prouver
Tri par insertion	Insérer chaque élément dans une partie déjà triée	Bon comportement sur une liste presque triée	Utilise des décalages plutôt que des échanges répétés
Tri fusion	Découper, trier, puis fusionner	Bon comportement sur de grandes listes	Demande une mémoire supplémentaire

Le tri fusion repose sur une autre stratégie : diviser pour régner. On coupe la liste en deux parties, on trie chaque partie, puis on fusionne les deux listes triées. Cette fusion consiste à comparer les premiers éléments de chaque partie, à prendre le plus petit, puis à continuer jusqu’à épuisement des deux parties.

Il n’est pas toujours nécessaire de savoir programmer tous les tris de mémoire. En revanche, il faut reconnaître leur principe, lire un code, suivre l’évolution d’une liste, et expliquer pourquoi l’algorithme se termine.

Correction, terminaison et invariants

Un algorithme de tri ne se valide pas seulement par quelques essais. Il faut savoir justifier qu’il fonctionne pour toute liste compatible avec son principe.

La terminaison signifie que l’algorithme finit par s’arrêter. Pour le tri par sélection, les boucles parcourent des indices bornés. Elles ne peuvent pas continuer indéfiniment. Pour le tri par insertion, l’indice qui se déplace vers la gauche diminue à chaque tour de la boucle interne. Il finit donc par sortir de la zone étudiée ou par trouver une valeur plus petite.

La correction signifie que le résultat obtenu est bien celui attendu. Pour l’établir, on utilise souvent un invariant de boucle.

• Dans le tri par sélection, après chaque passage, la partie gauche contient les plus petits éléments, triés.
• Dans le tri par insertion, avant chaque insertion, la partie gauche est déjà triée.
• Après la dernière étape, la partie étudiée correspond à toute la liste. La liste complète est donc triée.

Un invariant doit être vrai au départ, rester vrai après un tour de boucle, puis permettre de conclure à la fin. Cette structure donne une preuve claire et courte.

Attention aux erreurs classiques. Une boucle qui commence trop tôt ou s’arrête trop tard provoque souvent un accès hors de la liste. Un échange mal écrit peut perdre une valeur si on écrase une case avant de l’avoir mémorisée. Une condition mal choisie dans le tri par insertion peut empêcher la stabilité du tri.

Méthode le jour de l’évaluation

Commence par identifier le tri demandé. Cherche l’idée dominante : minimum à placer, élément à insérer, découpage en deux parties, fusion de listes triées. Ne pars pas directement dans le code.

1. Lis la consigne jusqu’au bout. Repère l’ordre demandé, croissant ou décroissant, et la structure utilisée, liste de nombres ou autre collection.
2. Trace les indices. Note ce que représentent i, j, indice_min ou la valeur mémorisée. Un indice n’est pas une valeur.
3. Fais un essai à la main. Utilise une petite liste, par exemple [4, 1, 3]. Écris chaque état de la liste après un échange ou une insertion.
4. Vérifie les bornes des boucles. Une liste de taille n possède des indices de 0 à n - 1. Cette règle évite la plupart des erreurs.
5. Explique l’invariant. Pour le tri par sélection, la partie gauche est triée et définitive. Pour le tri par insertion, la partie gauche est triée mais peut encore recevoir de nouveaux éléments.
6. Conclue proprement. Quand la zone triée recouvre toute la liste, le tri est terminé.

Si on demande de compléter un programme, lis les lignes déjà fournies. Elles indiquent souvent l’algorithme attendu. Si on demande une justification, n’écris pas seulement que « ça marche ». Donne la propriété conservée à chaque tour de boucle et explique pourquoi l’algorithme s’arrête.

Hugo Arbonnier