Trier des données permet ensuite de les chercher beaucoup plus vite. Tu vas étudier deux tris simples, le tri par sélection et le tri par insertion, mesurer leur coût, prouver qu’ils sont corrects grâce à un invariant de boucle, puis découvrir la recherche dichotomique, redoutablement efficace dans un tableau trié.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Écrire et dérouler le tri par sélection et le tri par insertion
- Justifier la correction d’un tri par un invariant de boucle
- Estimer le coût d’un algorithme : linéaire, quadratique, logarithmique
- Écrire et dérouler la recherche dichotomique, justifier sa terminaison par un variant
1. Le tri par sélection
Principe : on sélectionne le plus petit élément du tableau et on l’échange avec le premier ; puis on recommence sur la partie restante (à partir de l’indice 1), et ainsi de suite.
def tri_selection(T):
n = len(T)
for i in range(n - 1):
imin = i
for j in range(i + 1, n):
if T[j] < T[imin]:
imin = j
T[i], T[imin] = T[imin], T[i]Dérouler sur T = [5, 2, 8, 1, 9]
- i = 0 : minimum 1 (indice 3), échange avec T[0] → [1, 2, 8, 5, 9]
- i = 1 : minimum de [2, 8, 5, 9] : 2, déjà en place → [1, 2, 8, 5, 9]
- i = 2 : minimum de [8, 5, 9] : 5, échange → [1, 2, 5, 8, 9]
- i = 3 : minimum de [8, 9] : 8, déjà en place → [1, 2, 5, 8, 9]
Le tableau est trié ; il est modifié sur place (la fonction ne renvoie rien).
2. Le tri par insertion
Principe : comme quand on range des cartes dans sa main, on prend les éléments un par un et on insère chacun à sa place dans la partie gauche, déjà triée, en décalant vers la droite les éléments plus grands.
def tri_insertion(T):
for i in range(1, len(T)):
x = T[i]
j = i
while j > 0 and T[j - 1] > x:
T[j] = T[j - 1]
j = j - 1
T[j] = xDérouler sur T = [5, 2, 8, 1, 9]
- i = 1 : on insère 2 avant 5 → [2, 5, 8, 1, 9]
- i = 2 : 8 est déjà à sa place → [2, 5, 8, 1, 9]
- i = 3 : on insère 1 au début (8, 5 et 2 sont décalés) → [1, 2, 5, 8, 9]
- i = 4 : 9 est déjà à sa place → [1, 2, 5, 8, 9]
3. Coût des tris
On compte les comparaisons pour un tableau de n éléments. Le tri par sélection en fait toujours (n − 1) + (n − 2) + … + 1 = . Le tri par insertion en fait autant dans le pire cas (tableau trié à l’envers), mais seulement n − 1 si le tableau est déjà trié.
| n | 10 | 100 | 1 000 |
|---|---|---|---|
| 45 | 4 950 | 499 500 |
4. La recherche dichotomique
Dans un tableau trié, on compare la valeur cherchée à l’élément du milieu : selon le résultat, on élimine la moitié gauche ou la moitié droite. On recommence sur la moitié restante.
def dichotomie(T, v):
g, d = 0, len(T) - 1
while g <= d:
m = (g + d) // 2
if T[m] == v:
return m
elif T[m] < v:
g = m + 1
else:
d = m - 1
return -1Chercher 23 dans T = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
- g = 0, d = 9, m = 4 : T[4] = 16 < 23, donc g = 5
- g = 5, d = 9, m = 7 : T[7] = 56 > 23, donc d = 6
- g = 5, d = 6, m = 5 : T[5] = 23 : trouvé
La fonction renvoie 5 après 3 tours de boucle, au lieu de 6 comparaisons en recherche séquentielle.
À retenir
- Tri par sélection : chercher le minimum de la partie non triée et l’échanger avec le premier élément de cette partie.
- Tri par insertion : insérer chaque élément dans la partie gauche déjà triée.
- Un invariant de boucle prouve la correction ; les deux tris ont un coût quadratique (≈ n²).
- Recherche dichotomique : tableau trié obligatoire ; on divise la zone par 2 à chaque tour.
- Le variant d − g prouve la terminaison ; coût logarithmique (≈ log₂ n tours).
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.