Page Wikipedia

Tout le long de l'algorithme, on considère deux zones du tableau. L'une à gauche – sur fond orange dans l'exemple – et l'autre à droite – sur fond jaune dans l'exemple.

L'algorithme est constitué principalement d'une boucle répétitive. À chaque exécution de cette boucle, on sélectionne le plus petit élément parmi les jaunes et on le déplace à la suite de la zone orange. La zone orange s'en trouve augmentée d'un élément – ce qui diminue la jaune.

La boucle s'arrête quand la zone jaune ne compte plus qu'un seul élément. Le tableau est alors trié.

La recherche du plus petit élément est plus ou moins coûteuse selon le nombre d'items à considérer. Dans l'exemple, lors du premier passage, il faut chercher parmi 8 items ; lors du 2e passage, parmi 7 items… Ce cumul donne une bonne estimation du nombre de calculs élémentaires nécessaires pour ce tri :

$$8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36$$

On profite de notre travail sur les algorithmes de tri pour réfléchir aux problèmes de correction.

La boucle répétitive s'exécute tant qu'il reste plus d'un item dans la zone jaune.

On veut prouver qu'à la fin de l'algorithme, les items du tableau sont bien dans l'ordre croissant.

FONCTION tri_par_selection
ENTRÉE: tab, le tableau à trier
La fonction ne renvoie rien, le tableau est trié en place
DÉBUT
    soit n la longueur de tab
    POUR i ALLANT DE 0 À n - 2 FAIRE
        soit i_min, le rang du plus petit item dans tab à partir de i
        intervertir les items aux rangs i_min et i
    FIN
FIN

# recherche de i_min, rang du plus petit item,
# dans tab, à partir du rang i
soit i_min = i
POUR i ALLANT DE i À n - 1 FAIRE
    SI élément en j est plus petit que celui en i_min ALORS
        i_min = j
    FIN
FIN