Généralités

Le tri est un domaine important en programmation. Mais il l'est probablement beaucoup moins aujourd'hui qu'avant les années 1980. Cependant, il arrive parfois qu'on ait besoin de programmer un algorithme de tri, ou en tout cas, d'en choisir un. Parfois, on peut améliorer la performance par rapport à la fonction de tri existante grâce à la structure particulière de l'application. Dans ce cas, il est important de comprendre le comportement des algorithmes de base.

Une fonction générique de tri doit être paramétrée par une fonction de comparaison. Si cette fonction est triviale, le surcoût de l'appel de fonction peut être important par rapport à la comparaison proprement dite. C'est une autre situation où il peut être rentable d'écrire sa propre fonction de tri.

Il y a essentiellement trois types d'algorithmes raisonnables pour le tri. Dans la première catégorie, on trouve les algorithmes quadratiques, à savoir que leur performance au pire est $O(n^2)$. Ils sont parfois utilisables si leur comportement dans certains cas est meilleur que $O(n^2)$. Ce sont des algorithmes basés sur la comparaison entre deux éléments (tri par comparaison).

Dans la deuxième catégorie, on trouve les algorithmes dont la complexité est $O(n \texttt{log} n)$. Là aussi, il s'agit de tri par comparaison. L'algorithme de tri proposé par le système est presque toujours dans cette catégorie. En fait, c'est souvent l'algorithme de tri rapide (en Anglais : quicksort). On peut prouver que $O(n \texttt{log} n)$ est optimal pour les algorithmes de tri par comparaison.

Dans la dernière catégorie, on trouve des algorithmes linéaires, à savoir que leur complexité au pire est $O(n)$. Ce ne sont donc pas des algorithmes de tri par comparaison. Pour que ces algorithmes fonctionnent, le domaine des éléments à trier doit être compact et relativement petit (pas plus de quelques millions d'éléments).

Parfois, on souhaite trier tantôt par rapport à un critère, tantôt par rapport à un autre. Dans ce cas, on souhaite souvent préserver l'ordre entre deux éléments égaux par rapport au critère non utilisé pour le moment. Ceci est possible si l'algorithme de tri est stable. Un tel algorithme ne change pas l'ordre entre deux éléments égaux. Un algorithme de tri stable est souvent moins rapide qu'un algorithme qui se permet de changer l'ordre entre éléments égaux.

Certains algorithmes de tri nécessitent très peu de mémoire auxiliaire (un seul pointeur), alors que d'autres nécessitent de la mémoire auxiliaire de la taille de la structure (tableau ou liste) à trier. Les algorithmes de tri linéaires nécessitent de la mémoire auxiliaire de la taille du domaine à trier. Ceci était extrêmement critique il y a quelques décennies, mais l'est beaucoup moins maintenant. D'ailleurs à l'époque, on n'utilisait pas couramment les pointeurs et on triait des tableaux contenant directement les données. Dans ce cas, si la mémoire auxiliaire requise est de la taille du tableau initial, celle-ci peut effectivement prendre beaucoup de place. Aujourd'hui, les tableaux à trier contiennent le plus souvent des pointeurs vers les données. La taille du tableau est donc relativement petite par rapport à la taille des données. Par conséquent, même si l'algorithme de tri nécessite de la mémoire auxiliaire de la taille du tableau initial, cette taille reste souvent faible par rapport à la taille des données.

Il faut faire attention à la littérature sur les algorithmes de tri. Cette littérature a souvent été écrite il y a plusieurs dizaines d'années. Certains algorithmes ne sont pas traités car ils utilisent trop de mémoire auxiliaire, ou sont traités comme des algorithmes de tri uniquement sur mémoire secondaire (disque). Or aujourd'hui, ces algorithmes sont souvent pratiques (et même très bons) pour le tri en mémoire vive.