Le tri par sélection est un algorithme de tri simple. Cet algorithme de tri est un algorithme de comparaison sur place dans lequel la liste est divisée en deux parties, la partie triée à l’extrémité gauche et la partie non triée à l’extrémité droite. Initialement, la partie triée est vide et la partie non triée est la liste entière.
Le plus petit élément est sélectionné dans le tableau non trié et échangé avec l’élément le plus à gauche, et cet élément devient une partie du tableau trié. Ce processus continue de déplacer la limite de tableau non triée d’un élément vers la droite.
Cet algorithme ne convient pas aux grands ensembles de données car sa complexité moyenne et la pire des cas sont de Ο (n2), où n est le nombre d’éléments.
Comment Fonctionne le Tri par sélection?
Considérez le tableau représenté ci-dessous comme un exemple.
Pour la première position dans la liste triée, la liste entière est analysée séquentiellement. La première position où 14 est stockée actuellement, nous recherchons toute la liste et constatons que 10 est la valeur la plus basse.
Nous remplaçons donc 14 par 10. Après une itération, 10, qui se trouve être la valeur minimale dans la liste, apparaît en première position de la liste triée.
Pour la deuxième position, où réside 33, nous commençons à scanner le reste de la liste de manière linéaire.
Nous constatons que 14 est la deuxième valeur la plus basse de la liste et qu’elle devrait apparaître à la deuxième place. Nous échangeons ces valeurs.
Après deux itérations, deux valeurs minimales sont positionnées au début de manière triée.
Le même processus est appliqué au reste des éléments du tableau.
Voici une représentation picturale de l’ensemble du processus de tri −
Maintenant, apprenons quelques aspects de programmation du tri de sélection.
Algorithme
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
Pseudocode
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
Pour connaître l’implémentation du tri de sélection en langage de programmation C, veuillez cliquer ici.