Algorithmes Python

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.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

De la composition d'équipe au code
for start in range(len(result)):📍 La prochaine place libre dans la file
minimum = start🤔 Supposer que cette personne est la plus petite
result[index] < result[minimum]🔎 Chercher plus petit parmi les autres
result[start], result[minimum] = ...🔄 Placer le plus petit à la place libre
Un échange par position, après avoir parcouru toute la partie non triée.
En une phrase

Le 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

  1. Tout ce qui est à gauche de start est déjà trié ; tout ce qui part de start ne l'est pas.
  2. minimum retient l'indice de la plus petite valeur trouvée jusque-là dans la partie non triée.
  3. La boucle intérieure for index in range(start + 1, len(result)): parcourt le reste de la liste.
  4. 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

Exécuter le code →
main.py
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]))
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Échanger dans la boucle intérieure

Cela en fait un tri plus lent et plus brouillon, avec beaucoup d'échanges.

Problème
for index in range(start + 1, len(result)):
    if result[index] < result[start]:
        result[start], result[index] = result[index], result[start]
Correction
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.

Tous les défis