Numérique et sciences informatiques (spécialité) · Première · Algorithmique
Tris par insertion et par sélection
- Un tri range les éléments d'une liste dans l'ordre croissant ; le tri par sélection et le tri par insertion le font avec deux boucles imbriquées.
- Sélection : à chaque tour, on cherche le minimum de la partie non triée et on l'échange avec le premier élément de cette partie.
- Insertion : à chaque tour, on prend l'élément suivant et on le glisse à sa place dans la partie gauche, déjà triée.
- La correction se prouve par un invariant de boucle : au début du tour , les cases
t[0:i]sont triées.