Un tableau est une suite de valeurs. Trier ce tableau consiste à placer ces valeurs, par exemple, de la plus petite à la plus grande. Le résultat final peut être identique même si les méthodes diffèrent beaucoup. Nous utiliserons le petit tableau [5, 2, 4, 1], puis nous essaierons les trois méthodes sur 12 éléments dans le laboratoire visuel.
D’abord, comparaison et échange
Une comparaison répond à une question comme « 5 est-il supérieur à 2 ? ». Un échange inverse la position de deux éléments. Dans le laboratoire, chaque comparaison et chaque échange est une étape visible ; la durée de l’animation n’est pas le véritable temps de calcul.
Tri à bulles : le plus grand remonte à la fin
On compare deux voisins de gauche à droite. Si celui de gauche est plus grand, on les échange. Après un passage, la plus grande valeur encore à trier se trouve à droite ; les passages suivants peuvent l’ignorer.
- On part de [5, 2, 4, 1]. On échange 5 et 2 → [2, 5, 4, 1].
- On échange 5 et 4 → [2, 4, 5, 1], puis 5 et 1 → [2, 4, 1, 5]. Le 5 est à sa place définitive.
- Au passage suivant, 2 et 4 restent en place ; on échange 4 et 1 → [2, 1, 4, 5].
- Au dernier passage, on échange 2 et 1 → [1, 2, 4, 5].
La méthode est simple à suivre, mais un grand tableau peut demander beaucoup de comparaisons et d’échanges. Si un passage complet ne produit aucun échange, on peut s’arrêter.
Tri par sélection : chercher le minimum
On imagine une partie déjà triée à gauche et une partie encore à trier à droite. On cherche le minimum de la partie droite et on l’échange avec son premier élément libre. La partie triée grandit d’un élément.
- Dans [5, 2, 4, 1], le minimum est 1. On échange 5 et 1 → [1, 2, 4, 5].
- Parmi [2, 4, 5], le minimum est déjà 2 : aucun échange.
- Parmi [4, 5], le minimum est déjà 4. Le résultat est [1, 2, 4, 5].
Le nombre de comparaisons reste élevé même lorsque le tableau est déjà trié, mais il y a au plus un échange par position.
Tri par insertion : insérer dans la partie triée
Le premier élément, seul, est déjà trié. On prend le suivant et on le déplace vers la gauche jusqu’à sa bonne position dans le début déjà trié. Le laboratoire représente ce déplacement par une suite d’échanges entre voisins.
- On part de [5]. Insérer 2 avant 5 donne [2, 5, 4, 1].
- On insère 4 entre 2 et 5 → [2, 4, 5, 1].
- On insère 1 avant tous les autres → [1, 2, 4, 5].
Cette méthode convient particulièrement aux valeurs presque triées : chaque nouvel élément a peu de chemin à parcourir.
Qu’est-ce qui change vraiment ?
Les trois méthodes trient correctement, mais leurs opérations diffèrent. Le tri à bulles compare des voisins en plusieurs passages ; le tri par sélection cherche chaque minimum et limite les échanges ; le tri par insertion construit progressivement un début trié. Dans le pire cas, le travail augmente approximativement comme le carré de la taille du tableau. Avec 12 valeurs, comprendre la raison de chaque mouvement est plus utile que mesurer des millisecondes.