Упорядочить вслепую.

[BatMan]

лишнии 5$ никогда не помешают, только я у себя нашел

[nikvic]

BatMan в сообщении #803344 писал(а):

нашел 2 лишних сравнения)

По сравнению с картинкой?

[nikvic]

Остался вопрос про возможность доказательства нижней оценки. В лоб, перебором, явно не проходит...

[Sender]

Кстати, каково максимальное число транспозиций в минимальном разложении перестановки из 8 элементов?

[venco]

Sender в сообщении #803834 писал(а):

Кстати, каково максимальное число транспозиций в минимальном разложении перестановки из 8 элементов?

7?

[Sender]

Да, похоже на то. По крайней мере, мы имеем доказанную нижнюю оценку.

[Urnwestek]

nikvic в сообщении #803832 писал(а):

Остался вопрос про возможность доказательства нижней оценки. В лоб, перебором, явно не проходит...

Да вроде-таки в лоб и перебором. В энвики написано, что оптимальную сортирующую сеть из 8 элементов (с док-вом оптимальности, видимо) нашёл Кнут аж в 1997 году; и вот что-то мне не кажется, что было красивое доказательство нижней оценки с использованием, например, каких-то инвариантов, а кажется, что к 1997 году вычислительные мощности стали такими, что позволили сделать перебор.