précédent | suivant | table des matières
En avril 1991,dans BYTE magazine, un article de Stephen Lacey et Richard Box décrit le CombSort. Une modification simple de l’algorithme de tri par remontée des bulles permet de le rendre aussi efficace que les algorithmes de tri en tas ou de tri rapide. Dans le tri par remontée des bulles chaque élément est comparé au suivant, et éventuellement échangé si les deux éléments ne sont pas dans l’ordre. Apparaissent alors ce que les auteurs appellent des « tortues », c’est à dire des éléments qui sont loin de leurs places, et qui y vont lentement par échanges successifs. Leur idée est d’éliminer les tortues : au lieu de comparer des éléments successifs, on compare des éléments éloignés de tailleSaut, et on les échange s’ils ne sont pas dans l’ordre. Alors un élément devrait aller plus vite à sa place. A chaque étape, la valeur de tailleSaut est divisée par 1.3. La valeur 1.3 a été obtenue expérimentalement. L’algorithme se termine lorsqu’on a fait un passage avec tailleSaut égal à 1 et sans faire d’échanges : alors tous les éléments sont à leur place.
final double coeff = 1.3;
void combSort(int t [], int d, int f){
// tri du tableau t entre les indices d (inclus) et f (exclu)
int taille, tailleSaut;
boolean echange;
taille = f-d;
tailleSaut = taille;
echange = true;
while(echange || tailleSaut>1){
if(tailleSaut != 1)tailleSaut = (int)(tailleSaut/coeff);
echange = false;
for(int i = taille-1; i>=tailleSaut ; --i){
int j = i - tailleSaut;
if(t[i]<t[j]) { swap( t, i, j); echange = true; }
}
}
}