1. Présentation
Que se passe-t-il dans un tri ? On suppose qu'on se donne une suite de nombres entiers (ex: 5, 8, -3 ,6 ,42, 2,101, -8, 42, 6) et l'on souhaite les classer par ordre croissant (relation d'ordre au sens large). La suite précédente devient alors après le tri (classement) : (-8, -3, 2, 5, 6, 6, 8, 42, 42, 101). Il s'agit en fait d'une nouvelle suite obtenue par une permutation des éléments de la première liste de telle façon que les éléments résultants soient classés par ordre croissant au sens large selon la relation d'ordre totale " ≤ " : (-8 ≤ -3 ≤ 2 ≤ 5 ≤ 6 ≤ 6 ≤ 8 ≤ 42 ≤ 42 ≤ 101).
Cette opération se retrouve très souvent en informatique dans beaucoup de structures de données. Par exemple, il faut établir le classement de certains élèves, mettre en ordre un dictionnaire, trier l'index d'un livre, etc...
1.1. Tri interne, tri externe
Un tri interne s'effectue sur des données stockées dans une table en mémoire centrale, un tri externe est relatif à une structure de données non contenue entièrement dans la mémoire centrale (comme un fichier sur disque par exemple).
Dans certains cas les données peuvent être stockées sur disque (mémoire secondaire) mais structurées de telle façon à ce que chacune d'entre elles soit représentée en mémoire centrale par une clef associée à un pointeur. Le pointeur lié à la clef permet alors d'atteindre l'élément sur le disque (n° d'enregistrement...). Dans ce cas seules les clefs sont triées (en table ou en arbre) en mémoire centrale et il s'agit là d'un tri interne. Nous réservons le vocable tri externe uniquement aux manipulations de tris directement sur les données stockées en mémoire secondaire.
1.2. Des algorithmes classiques de tri interne
Dans les algorithmes référencés ci-dessous, nous notons (a1, a2, ... , an) la liste à trier. Etant donné le mode d'accès en mémoire centrale (accès direct aux données) une telle liste est généralement implantée selon un tableau à une dimension de n éléments (cas le plus courant).
Nous attachons dans les algorithmes présentés, à expliciter des tris majoritairement sur des tables, certains algorithmes utiliserons des structures d'arbres en mémoire centrale pour représenter notre liste à trier (a1, a2, ... , an).
Les opérations élémentaires principales les plus courantes permettant les calculs de complexité sur les tris, sont les suivantes :
- la comparaison de deux éléments de la liste ai et ak , (si ai > ak, si ai < ak,....)
- l'échange des places de deux éléments de la liste ai et ak , (place(ai ) <=> place( ak)).
Ce sont ces opérations qui seront utilisées pour fournir une mesure de comparaison des tris entre eux.