Vous aurez sûrement remarqué qu’il est plus rapide et plus simple de trouver quelque chose lorsque les données dans lesquelles on cherche sont triées.

C’est une chose que nous savons depuis qu’il existe des bibliothèques et des bibliothécaires : même si cela est long et fatigant, il vaut mieux ranger les livres d’une bibliothèque une fois pour toutes, par exemple dans l’ordre alphabétique, plutôt que les laisser en vrac et arpenter des kilomètres de rayonnages à chaque fois que l’on cherche un volume.

Cela mène naturellement à un nouveau problème : comment trier des données ? Selon le dictionnaire, “trier” signifie “répartir en plusieurs classes selon certains critères”. De manière plus restrictive, le terme de “tri” en algorithmique est très souvent attaché au processus de classement d'un ensemble d'éléments dans un ordre donné.

Par exemple, trier N entiers dans l'ordre croissant, ou N noms dans l'ordre alphabétique. Tout ensemble muni d'un ordre total peut fournir une suite d'éléments à trier.

Ainsi, pour trier des données, on utilise généralement des algorithmes de tri. Ils sont fondamentaux dans certains domaines, comme l'informatique de gestion où l'on tri de manière quasi-systématique des données avant de les utiliser.

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).

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.

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 :

• La complexité temporelle : mesure le nombre d'opérations élémentaires effectuées pour trier une collection d'éléments. C'est un critère majeur pour comparer les algorithmes de tri, puisque c'est une estimation directe du temps d'exécution de l'algorithme. (=complexité algo)

• La complexité spatiale : représente la quantité de mémoire dont va avoir besoin l'algorithme pour s'exécuter.

• Le caractère stable : Un tri est stable s’il préserve l’ordre d’apparition des objets en cas d’égalité des clés.