Exercice d’ informatique (5 points) 

Le tri par bulles.  L’ idée de cette méthode de tri consiste à imaginer que le tableau T[1] … T[n] de nombres à trier par ordre croissant est placé verticalement (T[n] en bas et T[1] en haut). Les nombres les plus petits remontent tels des bulles vers le haut du tableau comme suit. On effectue des passages successifs sur le tableau de bas en haut. A chaque étape élémentaire, si deux éléments sont en ordre inverse (le plus léger en dessous), on les échange. A la fin du premier passage, le plus petit nombre se trouve en première position (T[1]). A la fin du second passage, le deuxième plus petit nombre remonte en deuxième position  (T[2]) et ainsi de suite.  Remarquons :
 - que n-1 passages suffisent ;
 - qu’ il est inutile au deuxième passage d’ essayer de faire remonter l’ élément courant jusqu'à la première position. Plus généralement, le i-ème passage ne s’ intéresse qu’aux éléments situés entre le bas du tableau et la i-ème position.

Pour le tableau T ci-dessous,  voici un exemple d’ exécution :
 

T[1]	T[2]	T[3]	T[4]
20	10	15	5

 
premier passage :

20

10

5

15

 

20

5

10

15

 

5

20

10

15

deuxième passage :

5

20

10

15

 

5

10

20

15

troisième passage :

5

10

15

20

Complétez les pointillés pour obtenir une expression de l’ algorithme de tri  par bulles opérant sur tout tableau T[1] … T[n] :
 

pour i croissant de 1 jusqu'à ……  faire           pour j décroissant de n jusqu'à …… faire                 si T[j] < T[j-1] alors                  {échange de T[j] et T[j-1]}                 s <-- ……;                T[j] <-- ……;                 ……   <-- s;                 fin_si           fin_pour      fin_pour