Première · Numérique et sciences informatiques

Tris par insertion et par sélection

Savoir expliquer, dérouler à la main et comparer les algorithmes de tri par insertion et de tri par sélection sur une liste d'éléments comparables.

Aperçu gratuit
Illustration de la fiche « Tris par insertion et par sélection »

Les points essentiels

  • Un algorithme de tri range une liste dans un ordre fixé, par exemple l'ordre croissant.
  • Le tri par insertion construit une partie triée qui grandit de gauche à droite en insérant chaque nouvel élément à sa place.

Les mots à connaître

Tri
Réorganiser les éléments d'une liste selon un ordre choisi, par exemple du plus petit au plus grand.
Tri par insertion
Algorithme qui parcourt la liste de gauche à droite et insère chaque élément à sa place dans la partie déjà triée.

Un exemple pour comprendre

Dérouler le tri par insertion sur la liste [5, 2, 4, 1, 3].

Départ : [5, 2, 4, 1, 3]. Étape 1 : [5] est triée ; on insère 2 devant 5, liste [2, 5, 4, 1, 3]. Étape 2 : partie triée [2, 5] ; on insère 4 entre 2 et 5, liste [2, 4, 5, 1, 3]. Étape 3 : partie triée [2, 4, 5] ; on insère 1 au début, liste [1, 2, 4, 5, 3]. Étape 4 : partie triée [1, 2, 4, 5] ; on insère 3 entre 2 et 4, liste [1, 2, 3, 4, 5]. Résultat : [1, 2, 3, 4, 5].

Première page de l’Essentiel : Tris par insertion et par sélection
Ketty