L'algorithme
VARIABLE
t : tableau d'entiers
i : nombre entier
j : nombre entier
k : nombre entier
DEBUT
j←2
tant que j<=longueur(t): //boucle 1
i←j-1
k←t[j]
tant que i>0 et que t[i]>k: //boucle 2
t[i+1]←t[i]
i←i-1
fin tant que
t[i+1]←k
j←j+1
fin tant que
FIN
L'implémentation python
def tri_insertion(list):
n = len(list
for i in range(1, n):
# Stocker la valeur courante pour insertion ultérieure
cle = list[i]
j = i - 1
# Déplacer les éléments de la liste triée vers la droite
# jusqu'à ce qu'une position appropriée pour la valeur_courante soit trouvée
while j >= 0 and cle < list[j]:
list[j + 1] = list[j]
j -=
# Insérer la valeur_courante à sa position correcte
list[j + 1] = cle
# Exemple d'utilisation avec le liste (merci gabrielle) t
t = [4,1,3,5,2]
print(" liste (merci gabrielle) non trié :", t)
tri_insertion(t)
print(" liste (merci gabrielle) trié :", t)
L'algorithme
VARIABLE
t : tableau d'entiers
i : nombre entier
min : nombre entier
j : nombre entier
DEBUT
i←1
tant que i < longueur(t): //boucle 1
j←i+1
min←i
tant que j <= longueur(t): //boucle 2
si t[j] < t[min]:
min←j
fin si
j←j+1
fin tant que
si min≠i :
échanger t[i] et t[min]
fin si
i←i+1
fin tant que
FIN
L'implémentation python
def tri_selection(tab):
n = len(tab)
for i in range(n - 1):
# Trouver l'indice du minimum non trié
indice_min = i
for j in range(i + 1, n):
if tab[j] < tab[indice_min]:
indice_min = j
# Échanger l'élément minimum avec le premier élément non trié
tab[i], tab[indice_min] = tab[indice_min], tab[i]
print(tab)
# Exemple d'utilisation avec le tableau t
t = [15, 16, 11, 13, 12]
print("Tableau non trié :", t)
tri_selection(t)
print("Tableau trié :", t)
Exercices
Exercices de révisions
Exercice 1
Adapter le tri par insertion vu en cours pour trier le tableau de tuples suivants en fonction du second élément des tuples:
tab = [(5, "a"), (8, "b"), (1, "e"), (5, "d"), (7, "f"), (8, "c")]
Exercice 2
- Construire par compréhension un tableau de cent éléments aléatoires compris entre 0 et 10.
- En s’aidant du tri par insertion, écrire la fonction max_occurrences(tab: list) → int qui renvoie l’élément le plus présent dans le tableau.
Exercices epreuve pratiques
| Theme | Sujet 2024 | Exercice n° |
|---|---|---|
| Tri | 25/30/37 | 2 |
| insertion | 7/12 | 2 |
| Séléction | 12 | 1 |