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

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].

