Ce tri est une légère amélioration du tri bulle dans la
mesure où il permet non seulement aux plus grands éléments
de migrer vers la fin du vecteur mais aussi aux plus petits éléments
de se rapprocher du début du vecteur.
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
Et on retrouve après la montée du plus grand élément:
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.
Si on agit de même mais en partant du dernier
élément et en vérifiant si Ai>Ai+1 pour
i allant de N-2 à 1, le plus petit élément
prendra sa place définitive après la première
boucle:
Et on retrouve après la descente du plus petit élément:
Il suffit de recommencer ensuite le même processus avec
le morceau de A allant de la deuxième composante à
la N-1 ème. Cette fois, les boucles iront de 2 à
N-2 (et le N-1 ème élément est à sa
place définitive), et de N-3 à 2 (puisque le premier
élément est à sa place définitive).
Ainsi apparaissent un début et une fin de tableau triés.
Il faut recommencer jusqu'au moment où les indices de fin
et de début de morceaux classés se rejoignent ou aucun échange
n'a été effectué.