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