← Retour aux activités

Le Tri par Sélection

Le tri par sélection (ou selection sort) est un algorithme de tri simple. Son principe consiste à chercher le plus petit élément d'une liste et à le placer au début, puis à recommencer avec le reste de la liste.

1 Animation JavaScript

Cliquez sur "Démarrer" pour visualiser l'algorithme

Légende : ■ Minimum actuel | ■ Comparaison | ■ Déjà trié

2 L'Algorithme

PROCÉDURE tri_selection(tableau T) n = longueur(T) POUR i DE 0 À n-2 indice_min = i POUR j DE i+1 À n-1 SI T[j] < T[indice_min] ALORS indice_min = j FIN SI FIN POUR SI indice_min != i ALORS ECHANGER T[i] ET T[indice_min] FIN SI FIN POUR FIN PROCÉDURE
def tri_selection(tab): n = len(tab) for i in range(n - 1): indice_min = i for j in range(i + 1, n): if tab[j] < tab[indice_min]: indice_min = j if indice_min != i: tab[i], tab[indice_min] = tab[indice_min], tab[i] return tab

3 Complexité et Propriétés

Complexité temporelle

L'algorithme utilise deux boucles imbriquées :

Le nombre total de comparaisons est de l'ordre de $n^2$. La complexité est donc $O(n^2)$ dans tous les cas (meilleur, pire, moyen).

CasComplexité
Pire cas$O(n^2)$
Meilleur cas$O(n^2)$ (même si déjà trié, on doit tout comparer)

Terminaison

La terminaison est garantie par le fait que les boucles for s'effectuent sur des intervalles finis : de $0$ à $n-1$. L'indice de boucle progresse à chaque étape vers la borne supérieure.

Correction (Variant de boucle)

L'invariant de boucle est : "Après l'étape $i$, les $i+1$ premiers éléments sont triés et sont les plus petits du tableau initial."

4 Exercices d'application

Complétez les lignes de code manquantes pour que l'algorithme fonctionne correctement.

5 Défis de programmation

Série de 4 exercices thématiques pour approfondir la maîtrise du tri par sélection.