Prog-Info > C++ > Tri et Recherche > Tri shell.

Le tri Shell

C'est une variante du tri par insertion. Dans ce tri, les éléments sont décalés de plusieurs éléments. La distance qui les sépare est appelé "pas". A chaque étape le tableau est affiné (mieux organisé) et le pas réduit. Lorsque le pas est de 1, cela revient à un tri par insertion.
Le pas est généralement calculé à partir de la formule suivante :
u(n+1) = (3*u(n)+1) avec u(0) = 1.

void triShell(int 
        tableau[], const int longueur)

        {

           int pas, i, j, memoire;

           pas = 0;

        

           // Calcul du pas

           while(pas<longueur)

           {

              pas = 3*pas+1;

           }

        

           while(n!=0) // 
        tant que le pas est > 0

           {

pas = pas/3;

              for(i=n; 
        i<longueur; i++)



              {

                 memoire = tableau[i]; 
        // valeur à décaler éventuellement

                 j = i;

        

                 while((j>(pas-1)) 
        && (tableau[j-pas]>memoire))

                 { // 
        échange des valeurs

                    tableau[j] 
        = tableau[j-pas];

                    j 
        = j-pas;

                 }

                 tableau[j] = memoire;

              }

           }

        }

Exemple :
Calcul du pas pour un tableau de taille n = 100 :
u(0) = 0
u(1) = 3 * u(0) + 1 = 3 * 0 + 1 = 1
u(2) = 3 * u(1) + 1 = 3 * 1 + 1 = 4
u(3) = 3 * u(2) + 1 = 3 * 4 + 1 = 13
u(4) = 3 * u(3) + 1 = 3 * 13 + 1 = 40
u(5) = 3 * u(4) + 1 = 3 * 40 + 1 = 121
Les valeurs successives que la pas prendra seront donc :
pas1 = 121 / 3 = 40
pas2 = pas1 / 3 = 40 / 3 = 13
pas3 = pas2 / 3 = 13 / 3 = 4
pas4 = pas3 / 3 = 4 / 3 = 1

Les grandes étapes de l'algorithme :

53	31	10	87	13	59	62	26	47	38
13	31	10	87	53	59	62	26	47	38
13	31	10	87	53	59	62	26	47	38
13	31	10	87	53	59	62	26	47	38
13	31	10	26	53	59	62	87	47	38
13	31	10	26	47	59	62	87	53	38
13	31	10	26	47	38	62	87	53	59
maintenant le pas = 1 donc on passe à un tri par insertion
13	31	10	26	47	38	62	87	53	59
13	31	10	26	47	38	62	87	53	59
10	13	31	26	47	38	62	87	53	59
10	13	26	31	47	38	62	87	53	59
10	13	26	31	47	38	62	87	53	59
10	13	26	31	38	47	62	87	53	59
10	13	26	31	38	47	62	87	53	59
10	13	26	31	38	47	62	87	53	59
10	13	26	31	38	47	53	62	87	59
10	13	26	31	38	47	53	59	62	87

Complexité :
Le tri Shell est une excellente optimisation du tri par insertion. Le nombre d'opérations est de l'ordre de n*n.
En ce qui concerne la mémoire, très peu est nécessaire.