Tri par Sélection
Tri par Insertion
Bonus : Dénombrement
Bonus : Visualisation
Le Tri par Sélection
1. Le Concept
Le tri par sélection est intuitif : on cherche le plus petit élément de la liste et on le place en première position. Puis on cherche le plus petit parmi ceux qui restent, et on le place en seconde position, et ainsi de suite.
Algorithme en français :
- Parcourir toute la liste pour trouver le minimum.
- Échanger ce minimum avec le premier élément de la zone non triée.
- Répéter l'opération sur le reste de la liste (sans le premier élément désormais trié).
2. Exemple pas à pas
Liste initiale : [5, 2, 4, 6, 1, 3]
| Tour | Liste (Gras = Trié) | Action |
|---|---|---|
| Début | [5, 2, 4, 6, 1, 3] | Le minimum est 1 (index 4). On l'échange avec 5. |
| 1 | [**1**, 2, 4, 6, 5, 3] | Reste [2, 4, 6, 5, 3]. Le min est 2. Déjà bien placé. |
| 2 | [**1, 2**, 4, 6, 5, 3] | Reste [4, 6, 5, 3]. Le min est 3. On l'échange avec 4. |
| 3 | [**1, 2, 3**, 6, 5, 4] | Reste [6, 5, 4]. Le min est 4. On l'échange avec 6. |
| 4 | [**1, 2, 3, 4**, 5, 6] | Reste [5, 6]. Le min est 5. Déjà bien placé. |
| Fin | [**1, 2, 3, 4, 5**, 6] | Le dernier est forcément le plus grand. |
3. Visualisation Interactive
Tri par Sélection
Prêt à trier !
Vitesse
Trié
Comparaison
Échange
Min actuel
4. À vous de jouer !
Nous allons implémenter ce tri étape par étape.
Exercice A : Trouver le minimum
Écrire une fonction indice_min(liste, debut) qui renvoie l'indice de la valeur la plus petite dans la partie de la liste commençant à debut.
def indice_min(liste, debut):
# Votre code ici
pass
# Test : indice_min([5, 2, 4, 6, 1, 3], 0) doit renvoyer 4 (car 1 est à l'indice 4)
# Test : indice_min([5, 2, 4, 6, 1, 3], 2) doit renvoyer 5 (car 3 est le plus petit après l'indice 2)
Exercice B : L'algorithme complet
Utilisez la fonction précédente pour écrire tri_selection(liste).
Cette fonction ne renvoie rien mais modifie la liste directement (tri en place).
def tri_selection(liste):
# Pour chaque position i de 0 à la fin...
# 1. Trouver l'indice du minimum à partir de i
# 2. Échanger l'élément en i avec l'élément minimum trouvé
pass