Les algorithmes de tri

Illustration du tri rapide (quicksort) - Image de wikimedia commons sous licences CC, par simpsons contributor

L'informatique est, comme nous l'avons dit à de multiples reprises, la science du traitement de l'information. Parmi les opérations essentielles qui ressortent en terme de traitement des données, il y a les tris. Lorsque l'on a un jeu de données importants, il est souvent nécessaire, pour de multiples raisons, de commencer par le trier.

Cette prépondérance du tri est telle que lorsque D.E. Knuth a rédigé son ouvrage en 6 volume The art of computer Programming, le tome 3 entier a été consacré aux algorithmes de tri et de recherches.

Les tris sont aussi des algorithmes régulièrement étudiés pour apprendre l'informatique car ce sont des algorithmes classiques et qui introduisent de nombreuses structures ou concepts (le divisier pour régner du tri fusion par exemple, la notion d'arbres en tas du tri par tas, etc.)

Dans ce cours, nous allons voir quelques algorithmes de tri classique et quelques applications classiques du tri.