Pour i de 1 à Cpt-1 Faire 
Si t[i]>t[i+1] alors 
temp←t[i] 
t[i]←t[i+1] 
t[i+1]←t[i] 
Permut←Vrai 
FinSi 
FinPour 
FinTantQue 
FIN
Cependant si vous implémentez cet algorithme dans un quelconque langage vous allez vous apercevoir que celui­ci 
dans notre cas précis effectue une passe de trop. En effet dès le troisième passage le tableau est trié et pourtant le 
programme  continue.  C’est  que  lors  de  ce  passage  l’algorithme  a  effectué  une  permutation  des  deux  premières 
valeurs  17  et  9.  Partant  de  ce  fait,  l’indicateur  de  permutation  est  passé  à  Vrai  et  donc  une  nouvelle  boucle  est 
relancée. Comme il n’est pas possible de prévoir à l’avance le nombre de permutations restantes, l’algorithme montre 
ses limites dans ce cas précis. 
Si n est le nombre d’éléments du tableau, l’algorithme  effectue n­1 boucles  TantQue et n­1  boucles  Pour soit  (n­1)² 
boucles  ce  qui  se  développe  en  n²­2n+1.  La  complexité  est  d’ordre  O(n²).  Autrement  dit  la  complexité  de  cet 
algorithme est élevée. 
Remarquez aussi que cet algorithme balaie quoi qu’il arrive toutes les valeurs du tableau alors qu’on sait déjà qu’à la 
première passe la dernière valeur est la plus élevée, qu’à la seconde passe les deux dernières valeurs sont les plus 
élevées, et ainsi de suite. Il est donc possible d’optimiser l’algorithme en décrémentant de 1 la boucle Pour à chaque 
nouvelle passe. 
... 
DEBUT 
... 
Permut←vrai 
Cpt←5 
TantQue Permut Faire 
... 
Pour i de 1 à Cpt-1 
... 
FinPour 
Cpt←Cpt-1 
FinTantQue 
FIN
La complexité de cet algorithme est un peu moins élevée. En effet on effectue une boucle de moins à chaque passage. 
La complexité est cependant toujours en O(n²) : au premier passage il y a (n­1) comparaisons, au deuxième passage 
(n­2), au troisième (n­3) et ainsi de suite. On obtient donc une complexité de (n­1)+(n­2)+(n­3)+…+1 soit n(n­1)/2 et 
donc n²­n/2. C’est identique au tri par sélection. 
Le code Java correspondant est le suivant : 
class chap5_tribulle { 
public static void main(String[] args) { 
int t[]={14,13,12,11,10,9,8,7,6,5,4,3,2,1}; 
int i,cpt,temp; 
boolean Permut=true; 
 
cpt=13; 
while(Permut) { 
for(i=0;i<14;i++) System.out.print(t[i]+" "); 
System.out.println(); 
System.out.println("->"); 
Permut=false; 
for(i=0;i if(t[i]>t[i+1]) { 
temp=t[i]; 
t[i]=t[i+1]; 
t[i+1]=temp; 
Permut=true; 
} 
} 
cpt-; 
for(i=0;i<14;i++) System.out.print(t[i]+" "); 
System.out.println(); 
- 4 -
© ENI Editions - All rigths reserved - Jonifar lina
111