Objectifs
- Comprendre le tri par sélection et le tri par insertion
- Implémenter ces tris en Python (en place)
- Observer leur comportement avec les visualiseurs
- Découvrir un tri sans comparaison : le dénombrement
Idée clé
Trier, c'est réorganiser une liste pour que les éléments soient dans un ordre (croissant ou décroissant). Sélection et insertion procèdent par comparaisons ; le dénombrement compte les occurrences.
Niveaux de difficulté
Introduction, Facile, Moyen, Avancé, Difficile, Expert — puis choisis l'exercice.
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
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
Résultats attendus
- 1Après l'appel `tri_selection(ma_liste)`, résultat attendu : `ma_liste == [1, 2, 3, 4, 5, 6]`.
- 2Après l'appel `tri_selection(test_2)`, résultat attendu : `test_2 == [-2, 0, 10]`.
Piège fréquent
Confondre valeur et indice (surtout dans indice_min), ou oublier que le tri se fait en place : la liste passée en argument est modifiée.
À retenir
- Sélection : à chaque tour, placer le minimum de la zone non triée
- Insertion : prendre une « carte » et la glisser à sa place dans la zone déjà triée
- Les deux tris comparent des éléments deux à deux
- Le dénombrement compte les occurrences : rapide, mais limité aux entiers bornés
- Observer les visualiseurs aide à vérifier qu'on a bien compris l'invariant (zone triée / non triée)
- Pour aller plus loin : exercices sur le tri fusion
Pour s'entraîner
Compléter les onglets du TP ci-dessus, puis comparer sélection et insertion sur une liste déjà presque triée : lequel fait le moins de travail ?