Tri par Sélection
Invariant et complexité quadratique
Enonce
Implémenter le tri par sélection en place. À chaque étape $i$, trouver l'indice du minimum dans $T[i..n-1]$ et échanger avec $T[i]$.
⚠ Contrainte : Tri en place, retourne None.
Signature attendue
def tri_selection(T: list) -> None:Exemple
T = [64, 25, 12, 22, 11] ; tri_selection(T) ; T→[11, 12, 22, 25, 64]
📖 Rappel de cours
Le tri par sélection cherche à chaque étape le minimum du sous-tableau non trié et le place à sa position définitive.
🏆 Analogie — La file d'attente par taille :
Imaginez que vous devez ranger des élèves par taille. Vous parcourez toute la file, repérez le plus petit, et vous le placez en premier. Puis vous recommencez parmi ceux qui restent pour trouver le deuxième plus petit, etc. Vous « sélectionnez » toujours le minimum restant.
Invariant :
Après l'itération $i$, les éléments $T[0..i-1]$ sont les $i$ plus petits éléments du tableau, triés.
Complexité :
$C(n) = \sum_{i=0}^{n-2}(n-1-i) = \frac{n(n-1)}{2} = O(n^2)$
Le nombre de comparaisons est toujours $\frac{n(n-1)}{2}$, indépendamment de l'ordre initial.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Suite de Fibonacci
- Tri à Bulle (Bubble Sort)
- Tri par Insertion
- Tri Fusion (Merge Sort)
- Tri Rapide (Quicksort)
- Exponentiation Rapide
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.