Tri de shell

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) ; } .

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)
}