Tri par sélection

Le tri par sélection consiste à découper la liste en deux parties :

• Une partie triée située en début de liste (en jaune sur le schéma ci-contre)
• Une partie non triée située en fin de liste (en blanc sur le schéma ci-contre)

Initialement, la première partie est vide. Afin de la faire grossir, on va chercher dans la partie non triée la valeur la plus petite.

Une fois trouvée, elle est échangée avec la première valeur de la partie non triée, et la zone de la partie triée est étendue jusqu'à cette nouvelle valeur.

Une animation en ligne permet également de visualiser l'algorithme. Bien sélectionner SEL en haut.

Programmation en Python

Pour réaliser le tri par sélection en Python, il est plus pratique de séparer les étapes en fonctions pour simplifier le programme final :

• Une première fonction echange(l, i, j) permet d'échanger de place deux valeurs d'indices i et j dans la liste l.
  • Exemple : Si l = [1, 6, 4, 2], alors echange(l, 2, 3) modifie l, et si on print(l) on a comme affichage [1, 6, 2, 4].
• Une deuxième fonction indice_min(l, debut) renvoie l'indice de la valeur minimale dans l à partir de l'indice debut.
  • Exemple : Si l = [1, 6, 4, 2], alors indice_min(l, 1) regarde la valeur minimale à partir de l'indice 1 (valeur 6) et trouve 2 comme valeur minimale. La fonction renvoie donc 3 (l'indice de la valeur 2).
• La fonction principale tri_selection(l) qui trie la liste l.