Bonsoir !
Vous savez peut-être que le pas ou le gap n'est pas choisi au hasard. C'est toujours le plus grand terme de la suite de Donald Knuth mais inférieur au nombre de cases du tableau à trier.
1er terme = 1
terme suivant = 3 * terme précédent +1
Voici les premiers termes : 1, 4, 13, 40, 121, 364...
J'ai fait quelques recherches pour connaitre l'auteur de la suite. J'ai lu aussi, que la séquence de pas optimale n'est connue par personne. J'ai alors écrit un programme en PASCAL afin de comparer entre le tri par insertion et le tri Shell et j'ai trouvé qu'il faisait moins de décalages. Seulement, ce qui me gêne, c'est pourquoi est-ce que suite ou cet affinement du gap est plus efficace qu'un autre ?
Sur certaines autres pages, j'ai trouvé d'autres pas qui sont censés être une optimisation du tri par insertion aussi.
Si vous trouvez un site où l'affinement du gap est expliqué, je vous serais très reconnaissant de le partager avec moi.
Merci.