Tri par sélection : Implémentation et exécution

Introduction

Dans la leçon précédente, nous avons implémenté l'algorithme de recherche dichotomique et vu à quel point il est efficace. Cependant, sa grande force est aussi sa principale contrainte : il ne fonctionne que sur des données triées. Cela nous amène naturellement à la question : comment trier un ensemble de données qui ne l'est pas ?

Aujourd'hui, nous allons commencer à répondre à cette question en étudiant notre premier algorithme de tri : le tri par sélection. C'est un algorithme très intuitif qui ressemble à la manière dont un humain pourrait trier des objets. L'objectif est de vous rendre capable de comprendre sa logique, de l'implémenter en pseudo-code et, surtout, de tracer son exécution pas à pas.

1. Le principe du tri par sélection

L'idée du tri par sélection est simple et méthodique. Imaginez que vous avez un jeu de cartes en désordre dans la main. Comment pourriez-vous les trier par ordre croissant ? Une méthode serait de :

1. Parcourir toutes les cartes pour trouver la plus petite.
2. La prendre et la placer tout à gauche.
3. Recommencer l'opération avec les cartes restantes : chercher la plus petite parmi celles qui ne sont pas encore triées, et la placer juste à droite de la précédente.
4. Continuer jusqu'à ce que toutes les cartes soient à leur place.

L'algorithme de tri par sélection applique exactement cette logique à un tableau. À chaque étape, il "sélectionne" l'élément le plus petit de la partie non triée et l'échange avec l'élément qui se trouve au début de cette même partie.

Pour approfondir ce principe, je vous propose de lire la description suivante.

Pour résumer, l'algorithme maintient deux sous-tableaux à l'intérieur du tableau principal :

1. La partie de gauche, qui est déjà triée.
2. La partie de droite, qui reste à trier.

À chaque passage, il trouve le plus petit élément de la partie non triée et l'ajoute à la fin de la partie triée.

2. Tracer l'exécution de l'algorithme

Le traçage manuel est la meilleure façon de s'approprier la logique d'un algorithme. Suivons un exemple concret.

Prenons le tableau : [6, 1, 9, 3].

• Passe 1 :

  • Le tableau non trié est [6, 1, 9, 3].
  • On cherche le plus petit élément : c'est 1.
  • On échange 1 avec le premier élément de la zone non triée, qui est 6.
  • Le tableau devient : [1, 6, 9, 3]. La partie triée est maintenant [1].

• Passe 2 :

  • Le tableau non trié est [6, 9, 3] (commençant à l'index 1).
  • On cherche le plus petit élément : c'est 3.
  • On échange 3 avec le premier élément de la zone non triée, qui est 6.
  • Le tableau devient : [1, 3, 9, 6]. La partie triée est maintenant [1, 3].

• Passe 3 :

  • Le tableau non trié est [9, 6] (commençant à l'index 2).
  • On cherche le plus petit élément : c'est 6.
  • On échange 6 avec le premier élément de la zone non triée, qui est 9.
  • Le tableau devient : [1, 3, 6, 9]. La partie triée est maintenant [1, 3, 6].

Le dernier élément, 9, est maintenant forcément à la bonne place. Le tableau est trié !

L'image suivante illustre ce processus avec des couleurs pour bien distinguer la partie triée, la partie non triée et le minimum trouvé à chaque étape.

3. Formalisation en pseudo-code

Maintenant que la logique est claire, nous pouvons la traduire en pseudo-code. Pour cela, nous aurons besoin de deux boucles imbriquées :

• Une boucle principale (externe) qui parcourt le tableau pour définir la frontière entre la partie triée et la partie non triée. Appelons son compteur i.
• Une boucle secondaire (interne) qui parcourt la partie non triée (de l'indice i à la fin) pour trouver l'indice de l'élément minimum.

Voici à quoi ressemble l'algorithme en pseudo-code :

FONCTION tri_selection(tableau)
    // Entrée : un tableau de nombres
    // Sortie : le tableau est trié en place

    n ← longueur(tableau)

    // La boucle principale avance la frontière de la partie triée
    POUR i DE 0 À n - 2
        // On considère que le premier élément de la partie non triée est le minimum
        indice_min ← i

        // La boucle interne cherche le vrai minimum dans le reste du tableau
        POUR j DE i + 1 À n - 1
            // Si on trouve un élément plus petit...
            SI tableau[j] < tableau[indice_min] ALORS
                // ...on met à jour l'indice du minimum
                indice_min ← j
            FIN SI
        FIN POUR

        // Si le minimum n'est pas déjà à sa place, on l'échange
        // avec l'élément au début de la partie non triée.
        SI indice_min != i ALORS
            ECHANGER tableau[i] ET tableau[indice_min]
        FIN SI
    FIN POUR

    // Aucune valeur à retourner, le tableau est modifié directement ("en place")
FIN FONCTION

Quelques points importants sur ce pseudo-code :

• La boucle externe va de 0 à n - 2, car lorsque i atteint n-2, l'avant-dernier élément est mis à sa place. Le dernier élément (n-1) est alors automatiquement le plus grand et donc déjà trié.
• À chaque début de la boucle externe, indice_min est réinitialisé à i. C'est notre "meilleur candidat" pour le minimum jusqu'à présent.
• La boucle interne parcourt ce qui reste du tableau (DE i + 1 À n - 1) pour trouver le véritable minimum.
• L'échange (ECHANGER) se fait après la fin de la boucle interne. On ne fait qu'un seul échange par passe.

4. À vous de jouer !

Comme vous appréciez la pratique, voici un exercice pour vous assurer que tout est bien compris. Prenez une feuille et un crayon.

Exercice :
Triez la liste T = [42, 17, 9, 87, 23, 56] en utilisant l'algorithme du tri par sélection.
Pour chaque passe (chaque valeur de i de la boucle externe), écrivez :

1. L'indice et la valeur du minimum trouvé dans la partie non triée.
2. L'état du tableau après l'échange.

Conclusion

Félicitations ! Vous avez maintenant ajouté un premier et important algorithme de tri à votre boîte à outils. Bien qu'il ne soit pas le plus rapide pour de très grands tableaux, sa simplicité le rend facile à comprendre et à implémenter, ce qui en fait un excellent point de départ.

Points clés à retenir :

• Le tri par sélection divise le tableau en une partie triée et une partie non triée.
• Il fonctionne en trouvant itérativement le plus petit élément de la partie non triée et en l'échangeant avec le premier élément de cette partie.
• Son implémentation en pseudo-code repose sur deux boucles POUR imbriquées.
• Il effectue au maximum un seul échange par passe de la boucle principale.

Et après ?

Maintenant que vous maîtrisez le tri par sélection, nous allons explorer un autre algorithme de tri simple dans la prochaine leçon : le tri à bulles. Sa stratégie est différente : au lieu de chercher le minimum global, il se concentre sur des comparaisons et des échanges d'éléments adjacents. Cela nous permettra de comparer différentes approches pour résoudre le même problème.