Résumé Fiche BAC NSI — Algorithmes de tri : tout savoir pour décrocher les points

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 :