Les algorithmes de tri, principes et codes sources

​Les algorithme de tri font partie des notions les plus importantes en algorithmique, et ce cours vous permet d'appréhender cette notion avec beaucoup de facilité car vous allez pouvoir comprendre le principe d'un certain nombre d' algorithmes de tri avec des exemples animés, mais aussi voir en détail comment on peut coder cela en langage C. Vous avez ainsi la possibilité de comprendre et d'appliquer directement ces algorithmes.

Vous verrez aussi que nous traiterons ces algorithmes et leur programmation de façon itérative mais aussi en utilisant la récursivité des fonctions

vous aurez donc l'occasion d'appliquer plusieurs notions en même temps que l'apprentissage des algorithme de tri, ce qui va vous permettre de vous exercer encore plus et vous perfectionner en programmation.

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.

Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments et de la relation d’ordre associée. Un même algorithme peut par exemple être utilisé pour trier des réels selon la relation d'ordre usuelle « est inférieur ou égal à » et des chaînes de caractères selon l'ordre lexicographique. Ces algorithmes se prêtent naturellement à une implémentation polymorphe.

Les algorithmes de tri sont souvent étudiés dans les cours d'algorithmique pour introduire des notions comme la complexité algorithmique ou la terminaison.

La classification des algorithmes de tri est très importante, car elle permet de choisir l’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci. Les principales caractéristiques qui permettent de différencier les algorithmes de tri, outre leur principe de fonctionnement, sont la complexité temporelle, la complexité spatiale et le caractère stable.