J'aime bien cet algorithme de tri. De tous ceux que je vais expliquer c'est celui que j'utilise le plus souvent car il est aussi efficace qu'un autre tri basique et facile à programmer. Son principe est simple. On prend le premier élément et on recherche dans le reste du tableau l'élément le plus petit. Quand on le trouve, on inverse les deux, ensuite on refait pareil à partir du second élément, et ainsi de suite jusqu'au dernier.

Comme pour le tri par insertion, je vais l'illustrer avec un exemple. Imaginons que le tableau soit composé des chiffres suivants : 11, 2, 16, 10, 2, voici le déroulement de l'algorithme :



Je vais vous expliquer le principe même si à mon avis vous devez avoir compris. Au début, nous avons le tableau non trié 11, 2, 16, 10, 2. Nous regardons d'abord le plus petit élément du tableau, nous voyons que c'est 2. Nous inversons donc ce 2 avec le premier élément du tableau qui est 11. Nous ignorons donc le premier élément et nous rechercons à nouveau le minimum, qui ici est encore une fois 2. Nous inversons donc le deuxième élément avec l'élément 2 et comme tantot nous bloquons le 2. Nous sommes au troisième élément et nous recherchons le minimum qui est 10, nous inversons donc le 3ème élement avec l'élément qui vaut 10 et nous bloquons le troisième élément, ainsi de suite jusqu'à la fin du tableau, ainsi donc nous obtenons un tableau trié.

Complexité théorique temporelle

Avec x = 0, on effectue (N-1) comparaisons dans la boucle portant sur l'indice y, et 1 permutation.
Avec x = 1, on effectue (N-2) comparaisons et 1 permutation
...
Avec x = (N-3), on effectue 2 comparaisons et 1 permutation
Avec x = (N-2), on effectue 1 comparaison et 1 permutation

Au total, on effectue donc (N-1) + (N-2)+...+1 comparaisons (et (N-1) permutations), ce qui revient à dire que l'on a une CTT en O(N²).