, il n’est pas de bonne qualité, et pratiquement c’est même le plus mauvais tri.précédent | suivant | table des matières
L’idée consiste à comparer deux éléments adjacents, et à les échanger s’ils ne sont pas dans l’ordre. Lorsqu’on réalise un passage, on range le plus grand élément en fin de tableau ( ou le plus petit en début ). On a donc réalisé une partition entre l’élément le plus grand d’une part, et tous les autres éléments d’autre part.
void triBulles1(int t[]){
for (int i=t.length-1; i>=0; --i)
for (int j=0; j<i; ++j)
if (t[j+1] < t[j]) { // comparer deux voisins
int tmp = t[j]; // les échanger si nécessaire
t[j] = t[j+1];
t[j+1] = tmp;
}
}
L’algorithme est clairement en un nombre de comparaisons de l’ordre de , il n’est pas de bonne qualité, et pratiquement c’est même le plus mauvais tri.
|
On peut tenter d’accélérer l’algorithme en constatant que si le dernier échange se produit à l’indice dernierEchange, alors tous les éléments compris entre dernierEchange et i sont en ordre et à leur place. |
 |
void triBulles2(int t[]){
int dernierEchange;
for(int i=t.length-1; i>=0; ){
dernierEchange = -1;
for (int j=0; j<i; j++)
if (t[j+1] < t[j]) { // comparer deux voisins
int tmp = t[j]; // les échanger si nécessaire
t[j] = t[j+1];
t[j+1] = tmp;
dernierEchange = j;
}
i = dernierEchange;
}
}