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é. La complexité temporelle du tri boustrophédon est O(n^2), où n est le nombre d'éléments de la liste d'entrée. Il est donc moins efficace que d'autres algorithmes de tri courants tels que le quicksort et le mergesort, dont la complexité temporelle est respectivement de O(n log n) et O(n log n).

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