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 tri 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.
A priori, les algorithmes (par exemple les algorithmes de tri par insertion et de tri par sélection) "fonctionnent" correctement (dans nos exemples qu'ils trient bien le tableau donné en entrée), on dit que ces algorithmes sont corrects. On parle aussi de la "correction d'un algorithme" pour dire qu'un algorithme produit bien le résultat attendu.
Multiplier les exemples qui "fonctionnent" ne veut pas dire que l'algorithme donnera le "bon résultat" dans toutes les circonstances. C'est un peu comme en mathématiques, vérifier qu'une propriété est vraie sur un exemple n'a pas valeur de démonstration. Il se pourrait très bien que dans une situation donnée notre algorithme ne donne pas le résultat attendu.
Il existe un moyen de démontrer (au sens mathématique du terme) la correction d'un algorithme utilisant des boucles. Si nous arrivons à démontrer la correction d'un algorithme, nous pourrons alors affirmer que, quel que soit les données en entrée, nous obtiendrons bien en sortie le bon résultat. Pour démontrer la correction d'un algorithme, nous allons utiliser un "invariant de boucle".
Qu'est-ce qu'un invariant de boucle ?
On appelle invariant de boucle une propriété qui est vraie avant et après chaque itération.
Trouver ce qui pourrait être un invariant de boucle est une chose, encore faut-il ensuite démontrer qu'il est correct (une fois de plus l'étude d'un cas particulier ne vaut pas démonstration). La démonstration doit se faire en 3 étapes :
La notion de complexité d'un algorithme va rendre compte de l'efficacité de cet algorithme. Pour un même problème, par exemple trier un tableau, il existe plusieurs algorithmes, certains algorithmes sont plus efficaces que d'autres (par exemple un algorithme A mettra moins de temps qu'un algorithme B pour résoudre exactement le même problème, sur la même machine).
Il existe 2 types de complexité : une complexité en temps et une complexité en mémoire. Nous nous intéresserons ici uniquement à la complexité en temps. La complexité en temps est directement liée au nombre d'opérations élémentaires qui doivent être exécutées afin de résoudre un problème donné. L'évaluation de ce nombre d'opérations élémentaires n'est pas chose facile, on rencontre souvent des différences entre les cas.
Pour évaluer la complexité d'un algorithme, il faudra d'abord envisager le pire des cas. Puis en fonction du nombres n de données en entrée, on compte le nombre d'opérations pour obtenir le résultat. La complexité est l'ordre de grandeur du nombre d'opérations obtenues.