Tri par sélection (Selection Sort)

Le tri par sélection est un algorithme de tri simple utilisé pour organiser une liste d'éléments en ordre croissant ou décroissant. Son principe repose sur la recherche séquentielle de l'élément minimum (ou maximum) dans la liste non triée, puis sur l'échange de cet élément avec le premier élément de la liste non triée. Cette procédure est répétée en déplaçant progressivement la limite entre les parties triée et non triée de la liste, jusqu'à ce que tous les éléments soient correctement ordonnés.

Dans le détail, à chaque itération, le tri par sélection parcourt la liste pour trouver l'élément le plus petit dans la portion non triée et l'échange avec l'élément en première position de cette portion. Ensuite, la limite entre les parties triée et non triée est décalée d'une position, et le processus est répété jusqu'à ce que tous les éléments soient triés. Cela signifie que l'algorithme divise la liste en deux parties, l'une triée grandissant progressivement et l'autre non triée diminuant.

Le tri par sélection a une complexité en temps de O(n²), car il nécessite de parcourir la liste pour chaque élément afin de trouver le minimum, puis de faire un échange. Cette complexité reste la même dans le meilleur et le pire des cas, ce qui le rend moins efficace que d'autres algorithmes comme le tri rapide pour les grandes listes. Cependant, le tri par sélection est simple à implémenter et fonctionne bien sur de petites listes ou lorsque le coût des échanges est négligeable.

L'algorithme de tri par sélection n'est pas un algorithme stable, car des échanges peuvent modifier l'ordre relatif des éléments de même valeur. Il n'est pas non plus particulièrement efficace en termes de mémoire, mais il est en place, ce qui signifie qu'il trie directement dans la liste sans nécessiter de mémoire supplémentaire pour le stockage temporaire, contrairement à d'autres algorithmes de tri.

Le tri par sélection est souvent enseigné pour sa simplicité et pour illustrer les concepts de recherche et d'échange. Il est généralement préféré dans des contextes académiques ou pour des applications où la simplicité de l'algorithme prime sur les performances. Cependant, dans des applications réelles nécessitant des performances optimales, d'autres algorithmes, comme le tri par tas ou le tri rapide, sont généralement privilégiés pour les grandes quantités de données.

Principe du tri par sélection

Voici les principes détaillés étape par étape du tri par sélection :

• Initialiser la liste : Au départ, toute la liste est considérée comme non triée, et la partie triée est vide. La première position de la liste (index 0) est considérée comme le point de départ pour rechercher l'élément minimum.
• Trouver l'élément minimum : À chaque itération, l'algorithme parcourt la partie non triée de la liste pour identifier l'élément ayant la valeur la plus petite (ou la plus grande, si l'on souhaite un tri décroissant). Ce parcours commence à partir de la position actuelle, et se poursuit jusqu'à la fin de la liste.
• Échanger les éléments : Une fois l'élément minimum trouvé, il est échangé avec l'élément qui se trouve à la première position de la portion non triée. Après cet échange, l'élément minimum est maintenant placé à sa position correcte dans la liste triée.
• Réduire la portion non triée : Après chaque échange, la partie triée de la liste s'agrandit d'un élément (celui qui vient d'être inséré à sa place). La portion non triée diminue donc d'un élément, et l'algorithme passe à l'élément suivant dans la liste non triée.
• Répéter les étapes 2 à 4 : Les étapes 2 à 4 sont répétées pour chaque élément de la portion non triée restante. À chaque itération, un nouvel élément est ajouté à la portion triée, jusqu'à ce que toute la liste soit triée.
• Fin du tri : Lorsque la portion non triée devient vide, toute la liste est triée. L'algorithme s'arrête.

Algorithme

Voici l'algorithme de la tri par sélection :