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.
Choisir un exercice
Cliquer sur un exercice de la liste pour afficher son sujet.
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 ?