Les algorithmes de tri

Charles, professeur de la spécialité Numérique et sciences informatiques, propose un cours autour de la notion de tri.

Retrouvez en PDF : 

le support de cours,

des exercices autour de la notion de tri,

et la correction des exercices.

Pourquoi trie-t-on ?

Dans la vie courante, les deux verbes trier et classer ne sont pas synonymes.

→ Trier ou effectuer un tri c’est répartir les éléments en paquets correspondant à un certain critère : par exemple séparer les déchets selon leur nature, les personnes d’une assemblée selon leur sexe ou selon leur langue maternelle.

→ Classer ou effectuer un classement c’est mettre des éléments selon un certain ordre : par exemple ranger les personnes d’une assemblée de la plus petite à la plus grande, ou de la plus jeune à la plus âgée.

Un tri porte généralement sur un nombre assez important de données.

En informatique les mots tri et trier sont à prendre avec le sens de classement et classer. De nombreux algorithmes de tri existent, plus ou moins efficaces et plus ou moins faciles à mettre en œuvre. Ils peuvent permettre de classer une liste d’entiers dans le désordre dans l'ordre croissant.

Le tri par sélection. Principe et programme

Le tri par sélection est une méthode qui s’apparente à celle utilisée pour trier des copies suivant l’ordre décroissant des notes par exemple.

Le tri par insertion. Principe et programme

Le tri par insertion est une méthode très différente de la méthode de tri par sélection et s’apparente à celle utilisée pour trier ses cartes dans un jeu.