Contenu du chapitre

La notion d'algorithme peut être vue comme une abstraction de celle de programme: la même manière de trier une liste, d'ajouter deux nombres ou de compresser un fichier peut s'exprimer dans différents langages de programmation. Il existe donc un object abstrait, appelé algorithme, qui s'incarne dans ces programmes écrits dans différents langages. Ainsi, un algorithme peut se définir comme une manière particulière d'enchaîner des actions élémentaires pour résoudre toutes les instances d'un problème donné. L'autonomie de cette notion est renforcée par l'observation que, dans l'histoire de l'humanité, comme dans notre histoire personnelle d'ailleurs, il y a de nombreux algorithmes que nous avons su exécuter bien avant de savoir les exprimer dans un langage de programmation et même avant de savoir les verbaliser. Il y aussi de nombreux algorithmes qui s'exécutent dans notre cerveau, sans que nous sachions complètement les expliquer. Il y en a d'autres, comme certaines recettes de cuisine, que nous avons fini par réussir à verbaliser.

Ce chapitre a pour but de décrire quelques algorithmes de tri et de recherche sur des listes d'entiers et de comparer leur performance en terme de nombres de comparaisons et de déplacements ou échanges nécessaires.