Le tri par sélection (selection sort) en Python
Dans cette leçon, vous allez implémenter le tri par sélection en cherchant à chaque fois le plus petit élément pour le placer au bon endroit.
Introduction
Le problème
Certains algorithmes de tri cherchent à faire le moins de déplacements possible, ce qui compte quand déplacer un élément coûte cher. Le tri par sélection montre une autre stratégie que le tri à bulles : trouver d'abord le bon élément, puis le déplacer une seule fois.
Imaginez-le ainsi
Le tri par sélection, c'est comme composer une équipe par taille. Vous passez en revue tous ceux qui attendent encore, appelez le plus petit et le placez à la prochaine place de la file. Puis vous repassez en revue les autres pour le suivant, jusqu'à ce qu'il ne reste personne.
for start in range(len(result)):📍 La prochaine place libre dans la fileminimum = start🤔 Supposer que cette personne est la plus petiteresult[index] < result[minimum]🔎 Chercher plus petit parmi les autresresult[start], result[minimum] = ...🔄 Placer le plus petit à la place libreLe tri par sélection trouve encore et encore le plus petit élément de la partie non triée et l'échange avec la position suivante de la partie triée ; il fait O(n²) comparaisons mais au plus n - 1 échanges.
Points clés
- Tout ce qui est à gauche de
startest déjà trié ; tout ce qui part destartne l'est pas. minimumretient l'indice de la plus petite valeur trouvée jusque-là dans la partie non triée.- La boucle intérieure
for index in range(start + 1, len(result)):parcourt le reste de la liste. result[start], result[minimum] = result[minimum], result[start]fait un échange par position.
Quand l’utiliser ?
- Apprendre des stratégies de tri et les comparer.
- Les situations où écrire ou déplacer des éléments coûte cher et où comparer est bon marché.
- Trouver les k plus petits éléments en s'arrêtant après k passages.
Quand s'en passer
- Les vrais programmes :
sorted()est bien plus rapide. - Les données presque triées : le tri par sélection parcourt quand même tout, alors que le tri par insertion finit vite.
Visualisation de Le tri par sélection (selection sort) en Python
O(n²)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
def selection_sort(values):
result = values.copy()
for start in range(len(result)):
minimum = start
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
return result
print(selection_sort([64, 25, 12, 22, 11]))
Résultat de l’exécution
[11, 12, 22, 25, 64]
Explication du code
La variable minimum mémorise la position de la plus petite valeur dans le reste de la liste. À la fin de chaque passage, cette valeur est échangée avec la position start. L'algorithme a toujours une complexité de O(n²) à cause des nombreuses comparaisons, mais il fait au plus n échanges.
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Échanger dans la boucle intérieure
Cela en fait un tri plus lent et plus brouillon, avec beaucoup d'échanges.
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
- Minimum d’un tableau Trouvez la plus petite valeur dans une liste. Facile
- K-ième plus petit élément Trouvez la k-ième plus petite valeur sans trier entièrement. Moyen