précédent | suivant | table des matières

Le tri Shell.

Imaginé par Donald Lewis Shell  (``A high-speed sorting procedure,'' Communications of the ACM, 2:30, 1959.) ce tri est une accélération du tri par insertion. Dans le tri par insertion, un élément va à sa place en progressant lentement, case par case. L'accélération consiste à le faire aller à sa place en commençant par faire des grands pas, puis des pas de plus en plus petits, jusqu'à, évidemment, des pas de 1 pour que le tableau soit trié.

• L'étape de base de l'algorithme considère le tableau initial constitué de h sous-tableaux, dont les éléments sont distants de h cases. ces h tableaux sont triés par l'algorithme de tri par insertion. On dit alors que le tableau initial est h-trié.
• On répète cette opération de base pour des valeurs de h qui vont en diminuant jusqu'à une valeur finale 1.

La qualité du tri Shell va dépendre de la suite des valeurs de h. Une « bonne » suite est donnée par : 

void ShellSort(int a[]) {
    // calcul de la valeur initiale de h
    int h = 1;
    while ( h <= a.lenth) h = 3*h + 1;
    
    while ( h > 1) {
        h = h / 3;
        // tri par insertion des h tableaux
        for (int i = h; i < a.length; ++i){
            if (a[i] < a[i-h]) {
                 int   v = a[i], j = i;
                 while (j >= h  &&  a[j-h] > v) {
                       a[j] = a[j-h];
                       j = j - h;
                 };
                 a[j] = v;
            }
        }
    }
}

On peut imaginer d'autres suites pour h : ou encore un h tel que  

haut de la page