Tri boustrophedon

Le trie boustrophedon consiste à récupérer le minimum et le maximum à chaque itération et placer ces derniers respectivement au début et à la fin, l’ensemble de travail est alors décrémenté jusqu’à ce qu'il soit vide. Puisqu’à l'étape suivante on récupère également le minimum et le maximum alors :

• (1) { ∀ i,j ∈ [0..y] | i < j ∧ T[i] < T[j] } et (2) { ∀ i,j ∈ [N-y..N] | i < j ∧ T[i] < T[j] }
• (2) l'espace ce réduit à ?
• et par conjonction (3) { ∀ i,j ∈ [0..N] | i < j ∧ T[i] < T[j] }

qui résulte que le tableau est totalement trié.

Implémentation

template<typename T>
void boustrophedonsort(T *data, int count) noexcept
{
    int start = 0, end = count-1;

    while(end != start)
    {
        for(int i = start; i<end; ++i)
            if(data[i] > data[i+1])
              swap(data[i], data[i+1]);
        end--;

        assert(std::is_sorted(data+end, data+count)); // (1)

        if(end == start)
            break; // exit when count is odd

        for(int i = end; i>start; --i)
            if(data[i-1] > data[i])
              swap(data[i], data[i-1]);
        start++;

        assert(std::is_sorted(data, data+start-1)); // (2)
    }

    assert(std::is_sorted(data, data+count)); // (3)
}