Une liste mal ordonnée peut compliquer une recherche, un affichage ou un traitement de données. Le tri par sélection en Python permet de comprendre simplement comment un algorithme place progressivement chaque plus petite valeur au bon endroit, avec du code facile à lire, à tester et à modifier.
L’essentiel pour réussir un tri par sélection en Python
- Principe : chercher le plus petit élément dans la partie non triée, puis l’échanger avec le premier élément disponible.
- Complexité : environ O(n²) comparaisons, même lorsque la liste est presque triée.
- Avantage : un code court, pédagogique et peu gourmand en mémoire.
- Limite : cette méthode est généralement trop lente pour les grandes listes.
-
Usage courant : apprendre l’algorithmique plutôt que remplacer
sorted()dans une application réelle.
Comprendre le mécanisme sans se perdre dans la théorie
Le tri par sélection divise la liste en deux zones. À gauche, les éléments sont déjà dans le bon ordre. À droite, ils restent à examiner. À chaque passage, l’algorithme repère la plus petite valeur de la zone non triée, puis la place au début de cette zone.
Avec la liste [7, 3, 9, 2, 5], le premier passage cherche le minimum dans toute la liste et trouve 2. Il l’échange avec 7, ce qui donne [2, 3, 9, 7, 5]. Le deuxième passage recommence à partir de l’index 1 et cherche le plus petit élément parmi [3, 9, 7, 5].
- Repérer la position de départ de la zone non triée.
- Supposer que cette position contient déjà le minimum.
- Comparer cette valeur avec toutes les suivantes.
- Conserver l’index de la plus petite valeur trouvée.
- Effectuer un échange à la fin du passage.
Ce dernier point est important. L’algorithme ne déplace pas les éléments à chaque comparaison. Il effectue au maximum un échange par position, ce qui explique pourquoi il peut être intéressant lorsque le coût des écritures en mémoire compte davantage que celui des comparaisons.
Écrire une version Python claire et réutilisable
Voici une implémentation classique qui trie une copie de la liste. Je préfère cette forme pour les exemples, car elle évite de modifier silencieusement les données fournies par l’appelant.
def tri_selection(valeurs):
resultat = valeurs[:]
n = len(resultat)
for i in range(n - 1):
indice_min = i
for j in range(i + 1, n):
if resultat[j] < resultat[indice_min]:
indice_min = j
if indice_min != i:
resultat[i], resultat[indice_min] = (
resultat[indice_min],
resultat[i]
)
return resultat
nombres = [7, 3, 9, 2, 5]
print(tri_selection(nombres))
# [2, 3, 5, 7, 9]La variable i indique la position qui doit recevoir sa valeur définitive. La variable indice_min mémorise l’emplacement du plus petit élément découvert pendant le passage, tandis que j parcourt le reste de la liste.
La condition if indice_min != i n’est pas indispensable pour obtenir un résultat correct, mais elle évite un échange inutile lorsque le minimum se trouve déjà au bon endroit. Sur une petite liste, la différence est faible. Dans un code pédagogique, elle rend cependant l’intention beaucoup plus nette.
Lire aussi : Trier en Python - Maîtrisez `sort()` et `sorted()`
Version qui modifie directement la liste
Dans certains exercices, on attend une fonction qui trie la liste sur place. Elle ne crée donc pas de copie et retourne généralement la liste modifiée, même si l’on peut aussi choisir de retourner None comme le fait la méthode list.sort().
def tri_selection_sur_place(valeurs):
for i in range(len(valeurs) - 1):
indice_min = i
for j in range(i + 1, len(valeurs)):
if valeurs[j] < valeurs[indice_min]:
indice_min = j
valeurs[i], valeurs[indice_min] = (
valeurs[indice_min],
valeurs[i]
)
return valeursLe choix dépend du besoin. La copie protège la liste originale, tandis que le tri sur place utilise seulement un espace mémoire supplémentaire constant. Je recommande de préciser ce comportement dans le nom de la fonction ou dans sa documentation, car une modification involontaire est une source classique de bugs.
Suivre l’algorithme sur un exemple concret
Une trace manuelle permet de comprendre le rôle des deux boucles. Prenons [6, 1, 4, 2]. Au premier passage, la plus petite valeur est 1, qui prend la place de 6. La liste devient donc [1, 6, 4, 2].
| Passage | Zone examinée | Minimum trouvé | Liste après échange |
|---|---|---|---|
| 1 | [6, 1, 4, 2] |
1 |
[1, 6, 4, 2] |
| 2 | [6, 4, 2] |
2 |
[1, 2, 4, 6] |
| 3 | [4, 6] |
4 |
[1, 2, 4, 6] |
Après le troisième passage, il ne reste qu’un seul élément non placé. Il est forcément à la bonne position, ce qui explique pourquoi la boucle externe s’arrête à n - 1 plutôt qu’à n.
Le code fonctionne aussi avec des nombres négatifs, des doublons et une liste vide. En revanche, toutes les valeurs doivent pouvoir être comparées entre elles. Une liste contenant à la fois des entiers et des chaînes produira une erreur avec l’opérateur <.
Mesurer les performances et connaître les limites
Pour une liste de n éléments, le tri par sélection réalise environ n × (n - 1) / 2 comparaisons. Sa complexité temporelle est donc O(n²) dans le meilleur, le moyen et le pire cas. Même une liste déjà triée doit être parcourue pour vérifier chaque minimum.
| Critère | Tri par sélection | Conséquence pratique |
|---|---|---|
| Comparaisons | O(n²) |
Peu adapté aux grandes listes |
| Mémoire supplémentaire |
O(1) sur place |
Très économique en mémoire |
| Échanges | Au plus n - 1
|
Peut limiter les écritures |
| Stabilité | Non garantie | L’ordre des éléments égaux peut changer |
La stabilité signifie que deux éléments ayant la même clé conservent leur ordre d’origine. Le tri par sélection classique n’offre pas cette garantie, ce qui devient important lorsque l’on trie des objets selon un champ tout en voulant préserver un classement précédent.
Dans mes propres exercices, je réserve cette méthode aux listes de petite taille ou aux démonstrations d’algorithmique. Elle reste intéressante lorsque l’on veut limiter le nombre d’échanges, mais son coût en comparaisons devient vite dominant dès que la liste atteint plusieurs milliers d’éléments.
Choisir entre le tri manuel et les outils Python
Pour un programme applicatif, il faut généralement utiliser les outils intégrés au langage. sorted(valeurs) renvoie une nouvelle liste triée, tandis que valeurs.sort() modifie la liste existante et renvoie None.
valeurs = [7, 3, 9, 2, 5]
copie_triee = sorted(valeurs)
print(copie_triee)
print(valeurs)
# [2, 3, 5, 7, 9]
# [7, 3, 9, 2, 5]
valeurs.sort()
print(valeurs)
# [2, 3, 5, 7, 9]Ces fonctions intégrées sont stables, optimisées et généralement bien plus rapides qu’une implémentation pédagogique en Python. Elles acceptent aussi une fonction key pour trier des objets selon un attribut ou une transformation précise.
produits = [
{"nom": "Clavier", "prix": 45},
{"nom": "Souris", "prix": 25},
{"nom": "Écran", "prix": 180}
]
produits_tries = sorted(produits, key=lambda produit: produit["prix"])Le tri par sélection garde donc une vraie valeur pédagogique. Il permet de pratiquer les indices, les boucles imbriquées, les échanges et l’analyse de complexité, alors que sorted() répond mieux aux besoins d’un logiciel en production.
Ce que je vérifie avant de garder ce tri dans un projet
Avant d’utiliser cette méthode, je regarde d’abord la taille des données et la nécessité éventuelle de préserver l’ordre des doublons. Pour une liste de quelques dizaines d’éléments dans un exercice, le choix est parfaitement raisonnable. Pour un flux de données important, je préfère l’outil intégré de Python ou un algorithme mieux adapté.
- Tester une liste vide.
- Tester une liste avec un seul élément.
- Vérifier les doublons et les valeurs négatives.
- Décider clairement si la liste originale peut être modifiée.
- Comparer les performances sur des tailles représentatives.
Retenez surtout cette idée simple. Le tri par sélection est excellent pour comprendre ce qui se passe réellement dans un algorithme de tri, mais la simplicité du code ne signifie pas qu’il est le plus performant. En pratique, j’apprends son fonctionnement, puis je confie les grands volumes à sorted() ou à list.sort().
