Soit un vecteur A de dimension N. La méthode du tri consiste
tout d'abord à comparer Ai et Ai+1 et à échanger
ces deux éléments si Ai>Ai+1, et ceci pour tout
i allant de 1 à N-1.
Exemple: il faut trier
On compare les éléments en position 1 et 2 (en couleur rouge) pour éventuellement
les échanger
On les échange puisque'ils ne sont pas dans l'ordre croissant.
On compare les éléments en position 2 et 3 (en couleur rouge) pour éventuellement
les échanger
On les échange pour les mettre dans l'ordre croissant.
On compare les éléments en positions 3 et 4. Ils sont dans l'ordre
croissant; on n'y touche pas.
On compare les éléments en positions 4 et 5. Ils ne sont pas dans l'ordre
croissant; on les échange.
On compare les éléments en positions 5 et 6. Ils ne sont pas dans l'ordre
croissant; on les échange.
De la sorte les grands éléments ont tendance à
migrer vers la fin du vecteur. En particulier, au fur et à
mesure des échanges, la méthode fait avancer le
plus grand élément rencontré. A la fin de
la première boucle, AN contient le plus grand élément
du vecteur et cette Nème composante ne doit plus être
prise en compte dans la suite du tri puisqu'elle est à
sa place.
Il suffit de recommencer ensuite le même processus avec
le morceau de A allant de la première composante à
la N-1 ème. Cette fois, la boucle sur i ira de 1 à
N-2, et ainsi de suite.
Dans notre exemple, trions les éléments de position 1 à 5:
Si à une étape, on travaille jusqu'à l'indice
M<N (les éléments au-delà du M ème
occupent déjà leur position définitive),
l'élément en position M occupera lui aussi sa position
définitive et à l'étape suivante, seuls les
M-1 premiers éléments seront pris en compte. Mais
du fait de la tendance générale des plus grands
éléments à avancer, il est possible que les
éléments M-1, M-2, ... M-k occupent déjà
eux aussi leur position définitive et à l'étape
suivante on pourrait se contenter de ne considérer que
les M-k-1 premières composantes (au lieu des M-1 premières).
Cette situation peut être repérée en retenant
à partir de quel indice il n'a plus été nécessaire
de procéder à des échanges.
Nous devrions trier les éléments de position 1 à 4 mais
comme la dernière permutation concernait les éléments de position
1 et 2, le tri est terminé.