logo
Algorithme de tri
Selection & insertion

Selon le dictionnaire, « trier » signifie « répartir en plusieurs classes selon certains critères ». Le terme de « tri » en algorithmique est très souvent attaché au processus de classement d'un ensemble d'éléments dans un ordre donné. Par exemple, trier N entiers dans l'ordre croissant, ou N noms dans l'ordre alphabétique. Tout ensemble muni d'un ordre total peut fournir une suite d'éléments à trier.

Nous allons étudier ici 2 algorithmes de tri que vous devez connaître (tri par insertion et tri par selection).

Vous devez être capable d'en donner le principe ainsi que d'en évaluer la complexité.

Le tri par selection.

Consulter les liens ci-dessous sur l'algorithme par selection :

  1. Présentation.
  2. Présentation avec simulation.
  3. Etude de la complexité

Le tri par insertion.

Consulter les liens ci-dessous sur l'algorithme par insertion :

  1. Présentation.
  2. Présentation avec simulation.
  3. Etude de la complexité

Un autre simulateur de tri : xSortLab.

Encore un autre : visualgo.net

Encore un autre : inriamecsci.github.io

CCBYNCSA"

sources :  https://interstices.info/les-algorithmes-de-tri/   &   https://haltode.fr/articles.html

(Modifié C. Béasse - Juin 2019)