Tri par sélection
Cet algorithme de tri consiste à sélectionner le plus grand élément du tableau, à le mettre à la dernière place, puis à sélectionner le plus grand élément parmis ceux restants, à le mettre à l'avant-dernière place, et ainsi de suite.Pseudo-code
Entrée: T un tableau de n élémentsSortie: T a été modifié et est trié dans l'ordre croissant
Principe
L'indice j du pseudo-code correspond à chaque étape à l'indice du plus grand élément entre 0 et i: lorsqu'on l'a trouvé, on échange T[i] et T[j].Terminaison et complexité
Cet algorithme effectue au pire n tours de la boucle while car la boucle s'arrête lorsque i devient négatif, et i décroit strictement à chaque passage. Dans chaque passage, il faut faire une recherche de max en temps O(n). La complexité totale de l'algorithme est donc de O(n2) .Correction
A chaque passage sur la ligne 1, la condition suivante est vérifiée: "Les n-i-1 éléments les
plus grands sont positionnés dans l'ordre, dans les cases T[i+1], T[i+2], ..., T[n-1]".
En effet, au début de l'algorithme n-i-1 = 0, et chaque passage de boucle positionne un
élément de plus dans la bonne case.
Graphiquement, la partie en vert du tableau correspond au tableau trié final: les éléments y sont bien placés. C'est la partie qui est strictement après i.
A la fin de l'exécution, i vaut -1, et l'invariant devient: "les n éléments les plus grands sont positionnés dans l'ordre dans les cases T[0], ..., T[n-1]". Autrement dit, le tableau est trié.
Graphiquement, la partie en vert du tableau correspond au tableau trié final: les éléments y sont bien placés. C'est la partie qui est strictement après i.
A la fin de l'exécution, i vaut -1, et l'invariant devient: "les n éléments les plus grands sont positionnés dans l'ordre dans les cases T[0], ..., T[n-1]". Autrement dit, le tableau est trié.