ULUMINE · Numérique et sciences informatiques (NSI) · Première
Tris par sélection et par insertion, recherche dichotomique
Deux tris simples de coût quadratique et une recherche dichotomique de coût logarithmique dans un tableau trié.
Tris
- Sélection : pour i de 0 à n − 2, chercher le minimum de T[i…] et l’échanger avec T[i].
- Insertion : pour i de 1 à n − 1, insérer T[i] dans T[0…i − 1] trié en décalant les plus grands.
- Invariant : après le tour i, le début du tableau est trié.
- Coût : comparaisons au pire → quadratique ; insertion sur tableau trié : n − 1.
Dichotomie
- Tableau trié ; m = (g + d) // 2 ; g = m + 1 ou d = m − 1 ; on s’arrête si trouvé ou si g > d.
- Variant d − g : prouve la terminaison.
- ≈ log₂(n) tours : 10 pour 1 000, 20 pour un million.
Pièges à éviter
- Appliquer la dichotomie à un tableau non trié.
- Écrire g = m ou d = m (la boucle peut ne jamais s’arrêter).
- Confondre sélection (on cherche le minimum) et insertion (on décale).
- Penser qu’un tri renvoie un nouveau tableau : ici il modifie T sur place.