algorithme de tri

Imaginez cinq cartes portant les nombres 7, 3, 5, 2 et 5. Pour les ranger du plus petit au plus grand, il faut comparer leurs valeurs et déplacer celles qui ne sont pas à leur place. Un algorithme de tri décrit précisément cette suite d'actions et son point d'arrêt.

Le critère choisi décide du résultat : les mêmes fiches de personnes ne forment pas la même liste si elles sont classées par nom ou par âge.

Un algorithme de tri est une procédure finie qui reçoit une collection d'éléments et les réorganise selon une relation d'ordre fixée. Cette relation fournit le critère de comparaison : ordre numérique croissant, ordre alphabétique ou tout autre ordre défini pour les données. Le résultat doit contenir les mêmes éléments, avec les mêmes multiplicités, mais dans un ordre compatible avec ce critère.

Pour une liste de nombres notée a₁, …, a_n, où n est le nombre d'éléments, un tri croissant produit une liste notée b₁, …, b_n telle que b₁ ≤ … ≤ b_n. Les valeurs de la liste de sortie sont exactement celles de la liste d'entrée. Deux valeurs égales peuvent donc subsister.

Plusieurs procédures peuvent réaliser ce travail, notamment le tri par insertion, le tri à bulles, le tri fusion et le tri rapide. Leur choix ne dépend pas seulement du résultat attendu : la complexité temporelle estime la quantité d'opérations quand la taille de l'entrée augmente, tandis que la complexité spatiale mesure l'espace total utilisé. L'espace auxiliaire désigne plus précisément la mémoire supplémentaire requise.

On fixe d'abord une relation d'ordre et un sens de classement. Tant qu'il existe deux éléments consécutifs placés dans un ordre contraire au critère, la liste n'est pas triée. Une procédure de tri compare et déplace des éléments jusqu'à obtenir une suite ordonnée, sans ajouter ni perdre aucune occurrence. Pour un tri croissant, le point d'arrêt vérifie b_i ≤ b_i+1 pour chaque position i allant de 1 à n − 1.

Le tri exige des éléments comparables selon un même critère. La règle de comparaison doit être cohérente : pour les valeurs considérées, elle doit permettre de décider laquelle vient avant l'autre, et ses décisions ne doivent pas se contredire. Il faut aussi fixer le sens, par exemple croissant ou décroissant.

Un contre-cas apparaît si l'on mélange les critères en cours de route, par exemple en comparant certaines fiches par nom et d'autres par âge. La règle de comparaison n'est alors plus définie de manière unique ni garantie cohérente, même si la suite obtenue peut, par hasard, respecter un ordre. Il faut choisir une clé commune, ou définir plusieurs clés successives, puis appliquer cette même règle à toutes les comparaisons.

On veut trier par ordre croissant la liste 7, 3, 5, 2, 5 avec un tri par insertion. Les données sont les cinq valeurs de départ, et le critère place la plus petite valeur avant la plus grande. La partie gauche déjà traitée restera ordonnée après chaque insertion.

1. On insère 3 avant 7 : 3, 7, 5, 2, 5.
2. On insère le premier 5 entre 3 et 7 : 3, 5, 7, 2, 5.
3. On insère 2 avant 3 : 2, 3, 5, 7, 5.
4. On insère le dernier 5 avant 7 : 2, 3, 5, 5, 7.

Le résultat est 2, 3, 5, 5, 7. Le contrôle se fait en deux temps : chaque valeur est inférieure ou égale à la suivante, et les occurrences sont conservées, notamment les deux valeurs égales à 5. Le déroulé complet permet de suivre la zone déjà ordonnée à chaque étape.

Pour quelques cartes déjà presque rangées, le tri par insertion est naturel : on prend la carte suivante et on la glisse dans la partie déjà ordonnée. Le faible nombre de déplacements rend ce geste facile à suivre.

Pour une grande collection, le nombre d'éléments, l'ordre initial et la mémoire disponible deviennent des critères de choix. Le tri fusion et le tri rapide organisent les comparaisons autrement que le tri à bulles ou le tri par insertion.

Quand plusieurs éléments ont la même clé, comme deux fiches ayant le même âge, il faut décider si leur ordre initial doit être conservé. Cette exigence conduit à vérifier la stabilité de la méthode choisie, en plus de son temps d'exécution et de sa mémoire supplémentaire.

Trier et rechercher. Trier réorganise toute une collection selon un ordre ; rechercher vise à retrouver un élément. Obtenir la position du nombre 5 ne prouve pas que la liste entière est rangée.

Trier et filtrer. Trier conserve toutes les occurrences et change leur ordre ; filtrer retire les éléments qui ne satisfont pas un critère. La liste 7, 3, 5, 2, 5 triée contient encore cinq valeurs.

Algorithme et relation d'ordre. La relation fixe ce que signifie « avant » ; l'algorithme décrit les opérations qui produisent le rangement. Changer de relation peut changer le résultat sans changer le principe du tri.

Valeurs égales. Dans 2, 3, 5, 5, 7, les deux 5 sont correctement triés dans n'importe quel ordre entre eux. Si ces valeurs portent d'autres informations, il faut préciser si leur ordre initial doit être préservé.

Comparateur incohérent. Si le critère affirme qu'un élément vient avant un deuxième, le deuxième avant un troisième, puis le troisième avant le premier, le résultat ne peut pas former un ordre cohérent. Il faut corriger la règle de comparaison avant de trier.

Liste vide ou réduite à un élément. Aucun déplacement n'est nécessaire : la condition d'ordre est déjà satisfaite. Ce cas charnière doit être accepté sans tenter d'accéder à une paire d'éléments inexistante.

Même sortie, coûts différents. Deux algorithmes peuvent produire exactement 2, 3, 5, 5, 7 tout en effectuant un nombre d'opérations différent ou en utilisant une quantité différente de mémoire supplémentaire. Le résultat seul ne suffit donc pas à choisir la méthode.

Pour approfondir, on peut étudier séparément les trois questions qui distinguent les méthodes de tri : comment leur nombre d'opérations évolue avec la taille de l'entrée, quelle mémoire supplémentaire elles demandent et si elles conservent l'ordre initial des éléments de même clé. Ces critères permettent de comparer le tri par insertion, le tri à bulles, le tri fusion et le tri rapide sans confondre la correction du résultat avec le coût de son obtention.