Ha oui quand même, j'allais oublier le plus important ! Voici :
<<<<<<<<<<
Le tri shell
C'est une amélioration du tri par insertion : au lieu d'effectuer une rotation de tous les éléments entre la position initiale et finale (ou du moins meilleure) d'un élément, on peut faire des rotations par pas de P, ce qui rendra le fichier presque trié (chaque élément sera à moins de P positions de sa position exacte). On répète ce tri pour P diminuant jusqu'à 1. Une suite possible pour P est de finir par 1, les pas précédents étant de 4, 13, 40, 121, 364, 1093... (Pi=3*Pi-1 +1). D'autres suites sont évidement possibles, à condition de prendre des valeurs qui ne soient pas multiples entre elles (pour ne pas toujours traiter les mêmes éléments et laisser de côté les autres, par exemple les puissances successives de 2 ne traiteraient que les positions paires, sauf au dernier passage. Exemple d'implantation (shel_tus) :
void tri_shell_tus(type_tus tab, int N)
{
int pt,dpg,P; /* position testée,dernier plus grand */
composante tampon;
for(P=1;P<=N/9;P=3*P+1); /* calcul de P initial (<=N/9) */
for(;P>0;P/=3) /* inutile de soustraire 1 car division entière */
{
for(pt=P;pt<N;pt++)
{
dpg=pt-P;
tampon=tab[pt];
while(tab[dpg]>tampon&&dpg>=P-1)
{tab[dpg+P]=tab[dpg];dpg-=P;}
tab[dpg+P]=tampon;
}
}
}L'intérêt de ce tri, bien qu'il ait une boucle autour du tri par insertion, est qu'il crée rapidement un fichier presque trié, le dernier tri par insertion sera donc beaucoup plus rapide. Il est en général plus rapide que le tri par insertion pour les fichiers complètement mélangés, mais pour certains tableaux et pour certaines suites de P, il peut être bien plus mauvais que les autres tris.
>>>>>>>>>>
(de
ce site grâce auquel j'ai appris le C)
Et c'est toi qui te plains que moi, je suis insupportable? 
)
