Algorithmes de tri
Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle "est inférieur ou égal à". Les algorithmes de tris sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur.
La collection à trier est souvent donnée sous forme de tableau, afin de permettre l'accès direct aux différents éléments de la collection, ou sous forme de liste, ce qui peut se révéler être plus adapté à certains algorithmes et l'usage de la programmation fonctionnelle.
Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments de la relation d'ordre associée. Un même algorithme peut par exemple être utilisé pour trier les réels selon la relation d'ordre usuelle "est inférieur ou égal à" et des chaînes de caractères selon l'ordre lexicographique. Ces algorithmes se prêtent naturellement à une implémentation polymorphe (différents types).
Les algorithmes de tri sont souvent étudiés dans les cours d'algorithmique pour introduire des notions comme la complexité algorithmique ou la terminaison.