Fiche de révision — Algorithmes de tri | Terminale NSI
1. Tri par insertion
Principe : On parcourt le tableau de gauche à droite. Pour chaque élément, on l’insère à la bonne place dans la partie déjà
triée.
Complexité : - Meilleur cas (tableau déjà trié) : O(n) - Pire cas (tableau trié à l’envers) : O(n²) - Cas moyen : O(n²)
En place : Oui | Stable : Oui
Code Python :
def tri_insertion(tab):
for i in range(1, len(tab)):
cle = tab[i]
j = i - 1
while j >= 0 and tab[j] > cle:
tab[j + 1] = tab[j]
j -= 1
tab[j + 1] = cle
return tab
Invariant de boucle : À chaque itération i, le sous-tableau tab[0..i] est trié.
2. Tri par sélection
Principe : On cherche le minimum du tableau non trié et on le place en tête.
Complexité : - Tous les cas : O(n²)
En place : Oui | Stable : Non
Code Python :
def tri_selection(tab):
for i in range(len(tab)):
i_min = i
for j in range(i + 1, len(tab)):
if tab[j] < tab[i_min]:
i_min = j
tab[i], tab[i_min] = tab[i_min], tab[i]
return tab
Invariant de boucle : À chaque itération i, tab[0..i-1] contient les i plus petits éléments, triés.
3. Tri fusion (Merge Sort)
Principe : Diviser le tableau en deux moitiés, trier récursivement chaque moitié, puis fusionner.
Complexité : - Tous les cas : O(n log n)
En place : Non (nécessite de la mémoire supplémentaire) | Stable : Oui
Code Python :
1. Tri par insertion
Principe : On parcourt le tableau de gauche à droite. Pour chaque élément, on l’insère à la bonne place dans la partie déjà
triée.
Complexité : - Meilleur cas (tableau déjà trié) : O(n) - Pire cas (tableau trié à l’envers) : O(n²) - Cas moyen : O(n²)
En place : Oui | Stable : Oui
Code Python :
def tri_insertion(tab):
for i in range(1, len(tab)):
cle = tab[i]
j = i - 1
while j >= 0 and tab[j] > cle:
tab[j + 1] = tab[j]
j -= 1
tab[j + 1] = cle
return tab
Invariant de boucle : À chaque itération i, le sous-tableau tab[0..i] est trié.
2. Tri par sélection
Principe : On cherche le minimum du tableau non trié et on le place en tête.
Complexité : - Tous les cas : O(n²)
En place : Oui | Stable : Non
Code Python :
def tri_selection(tab):
for i in range(len(tab)):
i_min = i
for j in range(i + 1, len(tab)):
if tab[j] < tab[i_min]:
i_min = j
tab[i], tab[i_min] = tab[i_min], tab[i]
return tab
Invariant de boucle : À chaque itération i, tab[0..i-1] contient les i plus petits éléments, triés.
3. Tri fusion (Merge Sort)
Principe : Diviser le tableau en deux moitiés, trier récursivement chaque moitié, puis fusionner.
Complexité : - Tous les cas : O(n log n)
En place : Non (nécessite de la mémoire supplémentaire) | Stable : Oui
Code Python :
