Tri par insertion
Trier un tableau en prenant les éléments un par un et en les insérant à leur place dans la partie déjà triée : décalages, boucle intérieure, meilleur cas sur un tableau trié et stabilité.
- 25 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Tri par insertion : de quoi s'agit-il ?
Voir la réponse
Tri qui prend les éléments un à un et insère chacun à sa place dans la partie à sa gauche, déjà triée, en décalant les plus grands.
C'est la façon dont on range des cartes dans sa main : on prend la suivante et on la glisse là où elle va, en poussant les autres.
Qu'affiche ce programme ? Il montre le tableau après chaque insertion.
```python
t = [5, 2, 4, 6, 1]
for i in range(1, len(t)):
x = t[i]
j = i - 1
while j >= 0 and t[j] > x:
t[j + 1] = t[j]
j = j - 1
t[j + 1] = x
print(t)`[2, 5, 4, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 6, 1],[1, 2, 4, 5, 6][2, 5, 4, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 1, 6][2, 5, 4, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 1, 6],[1, 2, 4, 5, 6][1, 5, 2, 4, 6],[1, 2, 5, 4, 6],[1, 2, 4, 5, 6],[1, 2, 4, 5, 6]
Voir la réponse
[2, 5, 4, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 6, 1],[1, 2, 4, 5, 6]Insérer 2 décale le 5. Insérer 4 décale le 5. Insérer 6 ne décale rien (6 > 5) : le tableau ne change pas. Insérer 1 décale les quatre autres. Le dernier affichage est le tableau trié.
Dans le tri par insertion, la partie gauche du tableau est … ; l'élément à insérer est gardé dans une variable car sa case sera … par un décalage.
Voir la réponse
Dans le tri par insertion, la partie gauche du tableau est triée ; l'élément à insérer est gardé dans une variable car sa case sera écrasée par un décalage.
Sans cette copie, le premier décalage détruirait la valeur à insérer. La dernière ligne de la boucle écrit cette valeur dans la case libérée.
Décalage : de quoi s'agit-il ?
Voir la réponse
Recopie d'un élément dans la case voisine pour libérer la place où écrire l'élément à insérer.
Chaque décalage supprime exactement une inversion, c'est-à-dire un couple d'éléments rangés dans le mauvais ordre : le nombre de décalages est celui des inversions du tableau.