Tri de tableau + flag = tri à bulles

Et maintenant, nous en arrivons à la formule magique : tri de tableau + flag = tri à bulles.
L’idée de départ du tri à bulles consiste à se dire qu’un tableau trié en ordre croissant, c’est un tableau dans lequel tout élément est plus petit que celui qui le suit. Cette constatation percutante semble digne de M. de Lapalisse, un ancien voisin à moi. Mais elle est plus profonde – et plus utile - qu’elle n’en a l’air.
En effet, prenons chaque élément d’un tableau, et comparons-le avec l’élément qui le suit. Si l’ordre n’est pas bon, on permute ces deux éléments. Et on recommence jusqu’à ce que l’on n’ait plus aucune permutation à effectuer. Les éléments les plus grands « remontent » ainsi peu à peu vers les dernières places, ce qui explique la charmante dénomination de « tri à bulle ». Comme quoi l’algorithmique n’exclut pas un minimum syndical de sens poétique.
En quoi le tri à bulles implique-t-il l’utilisation d’un flag ? Eh bien, par ce qu’on ne sait jamais par avance combien de remontées de bulles on doit effectuer. En fait, tout ce qu’on peut dire, c’est qu’on devra effectuer le tri jusqu’à ce qu’il n’y ait plus d’éléments qui soient mal classés. Ceci est typiquement un cas de question « asymétrique » : il suffit que deux éléments soient mal classés pour qu’un tableau ne soit pas trié. En revanche, il faut que tous les éléments soient bien rangés pour que le tableau soit trié.
Nous baptiserons le flag Yapermute, car cette variable booléenne va nous indiquer si nous venons ou non de procéder à une permutation au cours du dernier balayage du tableau (dans le cas contraire, c’est signe que le tableau est trié, et donc qu’on peut arrêter la machine à bulles). La boucle principale sera alors :
Variable Yapermute en Booléen
Début
…
TantQue Yapermute
…
FinTantQue
Fin
Que va-t-on faire à l’intérieur de la boucle ? Prendre les éléments du tableau, du premier jusqu’à l’avant-dernier, et procéder à un échange si nécessaire. C’est parti :
Variable Yapermute en Booléen
Début
…
TantQue Yapermute
Pour i ← 0 à 10
Si t(i) > t(i+1) Alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Finsi
i suivant
Fin
Mais il ne faut pas oublier un détail capital : la gestion de notre flag. L’idée, c’est que cette variable va nous signaler le fait qu’il y a eu au moins une permutation effectuée. Il faut donc :
lui attribuer la valeur Vrai dès qu’une seule permutation a été faite (il suffit qu’il y en ait eu une seule pour qu’on doive tout recommencer encore une fois).
la remettre à Faux à chaque tour de la boucle principale (quand on recommence un nouveau tour général de bulles, il n’y a pas encore eu d’éléments échangés),
dernier point, il ne faut pas oublier de lancer la boucle principale, et pour cela de donner la valeur Vrai au flag au tout départ de l’algorithme.
La solution complète donne donc :
Variable Yapermute en Booléen
Début
…
Yapermut ← Vrai
TantQue Yapermut
Yapermut ← Faux
Pour i ← 0 à 10
Si t(i) > t(i+1) alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Yapermut ← Vrai
Finsi
i suivant
FinTantQue
Fin
Au risque de me répéter, la compréhension et la maîtrise du principe du flag font partie de l’arsenal du programmeur bien armé