Ceci est une ancienne révision du document !
Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon un ordre déterminé. Les objets à trier font donc partie d'un ensemble muni d'une relation d'ordre (de manière générale un ordre total). Les ordres les plus utilisés sont l’ordre numérique et l'ordre lexicographique (dictionnaire).
De plus, tous les algorithmes ne sont pas identiques, il existe plusieurs critères qui permettent des les différencier afin de choisir celui le plus adapté pour un cas. Les principales caractéristiques qui permettent de différencier les algorithmes de tri sont :
Un algorithme est dit stable s'il garde l'ordre relatif des quantités égales pour la relation d'ordre.
Tris par comparaison
Algorithmes lents :
On commence par chercher, parmi les objets à trier, un élément plus petit que tous les autres. Cet élément sera le premier du tableau trié. On cherche ensuite,parmi ceux qui restent, un élément plus petit que tous les autres, qui sera le deuxième du tableau trié, etc.
* Tri à bulles * Tri par insertion
Algorithmes rapides :
Tris utilisant la structure des données
Tri volumineux
Les algorithmes de tri doivent aussi être adaptés en fonction des configurations informatiques sur lesquels ils sont utilisés. Dans les exemples cités plus haut, on suppose que toutes les données sont présentes en mémoire centrale (ou accessibles en mémoire virtuelle). La situation se complexifie si l'on veut trier des volumes de données supérieurs à la mémoire centrale disponible (ou si l'on cherche à améliorer le tri en optimisant l'utilisation de la hiérarchie de mémoire).
Ces algorithmes sont souvent basés sur une approche assez voisine de celle du tri fusion. Le principe est le suivant :