Tri de shell

Le tri Shell est un algorithme de tri basé sur la comparaison en place qui a été développé par Donald Shell en 1959. Il s'agit d'une extension du tri par insertion, la différence essentielle étant que les éléments à comparer ne sont pas adjacents les uns aux autres, mais séparés par une certaine distance appelée "écart". L'écart est progressivement réduit jusqu'à ce qu'il devienne égal à 1. L'algorithme devient alors équivalent au tri par insertion.

Le principe du trie de shell repose sur le bubble sort, l'optimisation mise en œuvre consiste à faire un pré-tri :

• (2) { ∀ i,j ∈ [0..N] | i < j ∧ T[i] < T[j] ∧ i % offset = j % offset } <=> { is_shellphase_sorted(T, N, offset) ; }

dans des sous espaces induits par un offset afin de faire remonter une première fois les éléments > dans le haut du tableau, de sorte que la quantité de :

• ∀ i,j ∈ [0..N] | i <<< j ∧ T[i] < T[j]

soit vraie dans de plus en plus de cas au fur et a mesure que la granularité de l'algorithme diminue (l'offset) vers 1 la quantité ce transforme vers :

• ∀ i,j ∈ [0..N] | i << j ∧ T[i] < T[j]

pour atteindre l'assertion

• (1) { ∀ i,j ∈ [0..N] | i < j ∧ T[i] < T[j] }

lorsque l'offset = 1 (tableau trié). Pendant l'étape de tri, on faire remonter chaque élément n°y jusqu’à ce qu'il soit inférieur à un élément, puis on passe au suivant, donc tout les éléments avant sont inférieurs et triés :

• (3) { ∀ i,j ∈ [0..y] | i < j ∧ T[i] < T[j] ∧ i % offset = j % offset } <=> { is_shellphase_sorted(T, y, offset) ; } .

La complexité temporelle du tri de shell dépend de la séquence d'écarts utilisée, mais en général, elle est de O(n log n) dans le cas moyen et de O(n^2) dans le cas le plus défavorable, où n est le nombre d'éléments de la liste d'entrée. Toutefois, dans la pratique, il donne souvent de meilleurs résultats que d'autres algorithmes de tri à temps quadratique, tels que le tri à bulles et le tri par sélection. Le tri de shell est un algorithme efficace pour les listes de petite et moyenne taille, mais pour les très grandes listes, il est souvent surpassé par d'autres algorithmes de tri tels que le tri sélectif et le tri par fusion.

Implémentation

Vérification du trie interne

    // special "is_sorted" to use gap offset
    template<typename T>
    bool is_shellphase_sorted(const T *array, int length, int gap) noexcept
    {
        bool ordered = true;
        for(int i = gap; i < length-gap && ordered; i += gap)
            ordered &= array[i] < array[i+gap];
        return ordered;
    }

Trie des « couleurs »

    template<typename T>
    void shellsort_phase(T *array, int length, int gap) noexcept
    {
        for(int i = gap; i < length; i += gap)
        {
            int j, value = array[i];

            for(j = i - gap; j >= 0 && array[j] > value; j -= gap)
                array[j + gap] = array[j];
            array[j + gap] = value;

            assert(is_shellphase_sorted(array, j+gap+1, gap)); // (3)
        }

        // the subspace of the offset gap become sorted
        assert(is_shellphase_sorted(array, length, gap)); // (2)
    }

L'algorithme en lui même

template<typename T>
void shellsort(T *array, int length) noexcept
{
    /*
     * http://www.research.att.com/~njas/sequences/A102549
     * marcin ciura whitepaper
     *      http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf
     * best sequence for sorting ~4k element
     */

    static const int gaps[] = {
        1750, 701, 301, 132, 57, 23, 10, 4, 1
    };

    for(auto &it : gaps)
        shellsort_phase(array, length, it);

    // if gaps = 1 then shellsort is a bubblesort ; (automatic convergence)
    // the previous gaps is used to reduce the number of swap assertion then is not “necessary”
    assert(std::is_sorted(array, array+length)); // (1)
}

 De manière intéréssante, cette algorithme peut-être multi-threader :

template<typename T>
void shellsort(T *array, int length) noexcept
{
    // based on prime numbers, thus no overlaps between gaps
    static const int gaps[] = {
        1657, 1511, 1373, 1223, 1069,
        941, 809, 659, 541, 409, 281, 173, 71,
        37, 19, 11, 7, 5, 3
    };
    
    #pragma omp parallel for num_threads(6)
    for(auto &it : gaps)
        shellsort_phase(array, length, it);
    
    shellsort_phase(array, length, 1);
}