Le tri par sélection

Introduction du cours

Parmi les nombreux algorithmes de tri existants, celui dont je vais vous parler aujourd'hui a l'avantage d'être un des plus faciles à mettre en œuvre.
Même si je l'implémenterai ici avec une liste d'entiers, il fonctionne parfaitement avec n'importe quelle entité que l'on peut comparer (caractères, flottants, structures, etc...).

Principe

L'idée est simple : rechercher le plus grand élément (ou le plus petit), le placer en fin de tableau (ou en début), recommencer avec le second plus grand (ou le second plus petit), le placer en avant-dernière position (ou en seconde position) et ainsi de suite jusqu'à avoir parcouru la totalité du tableau.

Pour la suite du tuto ainsi que pour les différentes implémentations que je donnerai, j'appliquerai l'algorithme en recherchant l'élément le plus grand du tableau, et non le plus petit.

Cette décision est importante car à chaque fois que je déplacerai un élément en fin de tableau, je serai certain qu'il n'aura plus à être déplacé jusqu'à la fin du tri.

Regardons ensemble ce que donne l'algorithme appliqué à un exemple :

1. Soit le tableau d'entiers suivant :

   6

   2

   8

   1

   5

   3

   7

   9

   4

   0

2. L'élément le plus grand se trouve en 7ème position (si on commence à compter à partir de zéro) :

   6

   2

   8

   1

   5

   3

   7

   9

   4

   0

3. On échange l'élément le plus grand (en 7ème position) avec le dernier :

   6

   2

   8

   1

   5

   3

   7

   0

   4

   9

4. Le dernier élément du tableau est désormais forcément le plus grand. On continue donc en considérant le même tableau, en ignorant son dernier élément :

   6

   2

   8

   1

   5

   3

   7

   0

   4

   9

   Toute l'astuce de l'algorithme est là : on ignore volontairement dans la suite du traitement les éléments que l'on a déplacés à la fin du tableau.

5. De même, on repère l'élément le plus grand en ignorant le dernier et on l'échange avec l'avant dernier :

   6

   2

   4

   1

   5

   3

   7

   0

   8

   9

6. Et ainsi de suite, en ignorant à chaque fois les éléments déjà triés (en gras).

   6

   2

   4

   1

   5

   3

   0

   7

   8

   9

7. 0

   2

   4

   1

   5

   3

   6

   7

   8

   9

8. 0

   2

   4

   1

   3

   5

   6

   7

   8

   9

9. 0

   2

   3

   1

   4

   5

   6

   7

   8

   9

10. 0

    2

    1

    3

    4

    5

    6

    7

    8

    9

11. 0

    1

    2

    3

    4

    5

    6

    7

    8

    9

12. 0

    1

    2

    3

    4

    5

    6

    7

    8

    9

13. Et on a enfin trié notre tableau !

On sait que notre tableau est trié lorsque le nombre d'éléments non triés est égal à 1.

ImplémentationsImplémentation du tri d'un tableau

Maintenant que vous connaissez l'algorithme et que vous avez vu sur un exemple son fonctionnement, nous pouvons passer à son implémentation !

Mais avant cela, on remarque qu'il est possible de décomposer l'algorithme en plusieurs « sous-fonctions », ce qui facilitera notre travail :

• La recherche de l'élément le plus grand ;

• L'échange de deux éléments ;

• La réalisation du tri.

La fonction max()

Le fonctionnement de cette fonction (qui prend en paramètre un tableau et sa taille pour renvoyer l'indice de l'élément le plus grand) est simple : on se contente de parcourir l'intégralité du tableau pour à chaque fois comparer l'élément actuel avec le maximum provisoire.
J'ai choisi de ne conserver que l'indice du maximum provisoire, que je définis par défaut comme étant celui de la première valeur du tableau.

Le choix de cette valeur de départ est important ! En effet, si vous définissez directement une valeur telle que 0 et que votre tableau est du type {-6, -3, -2, -18}, votre algorithme renverra un maximum erroné !

/** * Renvoie l'indice du plus grand élément du tableau * * int tab[] :: tableau dans lequel on effectue la recherche * int taille :: taille du tableau * * return int l'indice du plus grand élément **/ int max(int tab[], int taille) { // on considère que le plus grand élément est le premier int i=0, indice_max=0; while(i < taille) { if(tab[i] > tab[indice_max]) indice_max = i; i++; } return indice_max; } La fonction echanger()

Le but ici est d'échanger deux éléments (dont on connait les indices) d'un tableau.
On agit de la même manière que lorsqu'on souhaite échanger le contenu de deux verres d'eau : on prend un troisième verre pour stocker temporairement un des contenus à échanger (l'image peut paraitre futile ou puérile, mais c'est exactement le comportement que reproduit cette petite fonction ;) ).

/** * Échange deux éléments d'un tableau * * int tab[] :: tableau dans lequel on effectue l'échange * int x :: indice du premier élément * int y :: indice du second élément * * return void **/ void echanger(int tab[], int x, int y) { int tmp; tmp = tab[x]; tab[x] = tab[y]; tab[y] = tmp; } La fonction tri_selection()

Petit exo du jour, bonjour ! (Eh oui, je ne vais quand même pas tout faire ... si ?)
Aujourd'hui et de manière totalement inopinée, je vais vous demander d'implémenter un algorithme qui vous est totalement inconnu ! Il est le suivant :

• Tant que la taille du tableau est supérieure à 0 :

• Rechercher l'indice de...