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
Légende : ■ Minimum actuel | ■ Comparaison | ■ Déjà trié
2 L'Algorithme
3 Complexité et Propriétés
Complexité temporelle
L'algorithme utilise deux boucles imbriquées :
- La boucle externe s'exécute $n-1$ fois.
- La boucle interne effectue environ $n/2$ comparaisons en moyenne.
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).
| Cas | Complexité |
|---|---|
| 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.