сортировка в лоб маленьких массивов

[fimadura]

Подскажите плиз, есть задача: написать программу, которая будет генерировать функции сортировки маленьких(2,3,4 и где-то до 10 элементов) массивов в лоб (например для двух, прога должна содержать один if, для трех, сортировать за три if'a и так далее). Соответственно, сгенерированная программа скорее всего не будет содержать циклов и будет работать только для массивов заданной длины.

Как тебе такой вариант: возьми сортировку вставкой и от-unroll'ь циклы для заданного N, т.е.

if (a[0] < a[1]) swap(a[0], a[1]);
// инвариант: a[0]<=a[1] 
if (a[1] < a[2]) swap(a[1], a[2]);
if (a[0] < a[2]) swap(a[0], a[2]);
// инвариант: a[0]<=a[1]<=a[2]
if (a[2] < a[3]) swap(a[2], a[3]);
if (a[1] < a[3]) swap(a[1], a[3]);
if (a[0] < a[3]) swap(a[0], a[3]);
// инвариант: a[0]<=a[1]<=a[2]<=a[3]
...

Извиняюсь, код должен выглядеть так

if (a[0] > a[1]) swap(a[0], a[1]);
...
if (a[1] > a[2]) swap(a[1], a[2]);
if (a[0] > a[1]) swap(a[0], a[1]);
...
if (a[2] > a[3]) swap(a[2], a[3]);
if (a[1] > a[2]) swap(a[1], a[2]);
if (a[0] > a[1]) swap(a[0], a[1]);
...

[MBo]

Например, 5 элементов можно отсортировать за 7 сравнений - но это весьма нетривиально (описание есть на этом сайте). Так нужно ли добиваться минимального количества сравнений?

возможно, стоит посмотреть на сортирующие сети.

Да нужно именно за 7 сравнений. А ткни плиз в ссылку на сайте. Если сделать unroll какого-нибудь алгоритма, то имхо там получится несколько больше чем nlogn действий (если только это не пирамидальная сортировка). Но хочется чтоб функция сортировки n-элементного массива генерировалась автоматически на этапе компиляции (для заданных n)

[MBo]

http://algolist.ru/olimp/sor_prb.php