Подтвердить что ты не робот

Стандартные сортировочные сети при малых значениях n

Я ищу реализацию сортировочной сети для 5-элементной сортировки, но поскольку я не смог найти хорошую ссылку на SO, я бы попросил сортировать сети для всех малых значений n, по крайней мере n = 3 до n = 6, но более высокие значения также будут большими. Хороший ответ должен, по крайней мере, перечислить их как последовательности операций "своп" (сортировка по 2 элементам), но также было бы неплохо увидеть рекурсивную декомпозицию в терминах сетей сортировки более низкого порядка.

Для моего приложения я на самом деле забочусь только о медиане 5 элементов, а не о том, чтобы привести их в порядок. То есть порядок остальных 4 элементов может быть неуказан в результате, пока медиана окажется в нужном месте. Можно ли использовать подход, связанный с сортировкой сетей, для вычисления медианы с меньшим количеством свопов, чем при выполнении полного сортировки? Если это так, то такое решение моей проблемы (для n = 5) и для других случаев тоже сделало бы большой ответ.

(Примечание: я отметил этот вопрос C, потому что C - это язык, который я использую, и я подозреваю, что люди, которые следуют тегу C, имеют хорошие ответы, но мне все равно, действительно ли ответ написан на C по сравнению с псевдо -код до тех пор, пока он легко переводит на С, что он должен делать естественно, если удовлетворяются вышеупомянутые критерии.)

4b9b3361

ОТВЕТЫ

Ответ 1

Выберите один из каждого раздела, предположительно в зависимости от того, что быстрее всего работает на вашем оборудовании, так как мы твердо находимся в сфере "дьявольской оптимизации": http://smarterrecall.com/networks.html, воспроизводится ниже:

Я создал этот сайт, чтобы перечислить все возможные оптимальные сети сортировки до 6 входов, написанных с использованием программы в Matlab. Самое длинное время выполнения - 5 входов на 45 секунд. Если вы заинтересованы в контакте со мной, меня можно найти на rpl1 [AT] rice [DOT] edu Ура, Ричард Л.

----------

 - 2-input: 1 network

    [[1 2]]


----------


 - 3-input: 6 networks

[[1 2][1 3][2 3]]
[[1 2][2 3][1 2]]
[[1 3][1 2][2 3]]
[[1 3][2 3][1 2]]
[[2 3][1 2][2 3]]
[[2 3][1 3][1 2]]


----------

 - 4-input: 3 networks

[[1 2][3 4][1 3][2 4][2 3]]
[[1 3][2 4][1 2][3 4][2 3]]
[[1 4][2 3][1 2][3 4][2 3]]


----------

 - 5-input: 180 networks

    [[1 2][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 2][3 4][1 3][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 4][1 3][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 2][3 4][1 3][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 2][3 4][1 4][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 4][1 4][3 5][1 3][2 5][2 3][4 5][3 4]]
    [[1 2][3 4][1 5][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 2][3 4][1 5][2 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 2][3 4][1 5][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 2][3 4][2 4][3 5][1 2][4 5][1 3][2 4][2 3]]
    [[1 2][3 4][2 4][3 5][1 3][2 5][2 3][4 5][3 4]]
    [[1 2][3 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 2][3 5][1 3][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 5][1 3][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 2][3 5][1 3][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 2][3 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 2][3 5][1 4][2 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][3 5][1 4][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 5][1 5][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 5][1 5][3 4][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][3 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 2][3 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[1 2][3 5][2 5][3 4][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][4 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 2][4 5][1 3][2 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 2][4 5][1 3][2 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 2][4 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 2][4 5][1 4][2 3][2 4][3 5][1 2][3 4][2 3]]
    [[1 2][4 5][1 4][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][4 5][1 4][3 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 2][4 5][1 5][2 3][2 4][3 5][1 2][3 4][2 3]]
    [[1 2][4 5][1 5][3 4][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][4 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 2][4 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[1 2][4 5][2 5][3 4][1 3][2 4][2 3][4 5][3 4]]
    [[1 3][2 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 3][2 4][1 2][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 4][1 2][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 3][2 4][1 2][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][2 4][1 4][2 5][1 2][3 5][2 3][4 5][3 4]]
    [[1 3][2 4][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 4][1 5][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 3][2 4][1 5][3 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 3][2 4][1 5][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 3][2 4][2 5][3 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 3][2 4][2 5][3 4][1 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 3][2 5][1 2][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 5][1 2][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 3][2 5][1 2][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][2 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 3][2 5][1 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][2 5][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][2 5][1 5][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 3][2 5][2 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][2 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 3][4 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 3][4 5][1 2][3 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 3][4 5][1 2][3 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 3][4 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 3][4 5][1 4][2 3][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][4 5][1 4][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][4 5][1 4][2 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][4 5][1 5][2 3][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][4 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][4 5][2 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][4 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 3][4 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[1 4][2 3][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 4][2 3][1 2][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 3][1 2][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 4][2 3][1 2][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 4][2 3][1 3][2 5][1 2][4 5][2 4][3 5][3 4]]
    [[1 4][2 3][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 4][2 3][1 5][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][2 3][1 5][3 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][2 3][1 5][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 3][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 3][2 5][3 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][2 3][2 5][3 4][1 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 4][2 5][1 2][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 5][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 4][2 5][1 2][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][2 5][1 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][2 5][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 4][2 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][2 5][1 5][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 5][2 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][2 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 4][2 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 4][3 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 4][3 5][1 2][4 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 4][3 5][1 2][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 4][3 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][3 5][1 3][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][3 5][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][3 5][1 3][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][3 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][3 5][1 5][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][3 5][2 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][3 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 4][3 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[1 5][2 3][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 5][2 3][1 2][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 3][1 2][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 5][2 3][1 2][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 5][2 3][1 3][2 4][1 2][4 5][2 4][3 5][3 4]]
    [[1 5][2 3][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 5][2 3][1 4][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 3][1 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 3][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 3][2 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 3][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 3][2 5][3 4][1 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 4][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 5][2 4][1 2][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 5][2 4][1 2][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 4][1 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 4][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 5][2 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]]
    [[1 5][2 4][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 4][2 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 5][2 4][2 5][3 4][1 3][4 5][1 2][3 4][2 3]]
    [[1 5][3 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 5][3 4][1 2][4 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 5][3 4][1 2][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 5][3 4][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 5][3 4][1 3][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][3 4][1 3][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][3 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]]
    [[1 5][3 4][1 4][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][3 4][2 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][3 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 5][3 4][2 4][3 5][1 2][4 5][1 3][2 4][2 3]]
    [[2 3][4 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[2 3][4 5][1 2][3 5][1 4][2 3][2 4][3 5][3 4]]
    [[2 3][4 5][1 2][3 5][2 5][3 4][1 3][2 4][2 3]]
    [[2 3][4 5][1 3][2 4][1 2][4 5][2 4][3 5][3 4]]
    [[2 3][4 5][1 3][2 4][1 4][3 5][1 2][3 4][2 3]]
    [[2 3][4 5][1 3][2 5][1 4][3 5][1 2][3 4][2 3]]
    [[2 3][4 5][1 4][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 3][4 5][1 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 3][4 5][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[2 3][4 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]]
    [[2 3][4 5][1 5][2 4][1 4][3 5][1 2][3 4][2 3]]
    [[2 3][4 5][1 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[2 4][3 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[2 4][3 5][1 2][4 5][1 3][2 4][2 3][4 5][3 4]]
    [[2 4][3 5][1 2][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[2 4][3 5][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 4][3 5][1 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 4][3 5][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[2 4][3 5][1 4][2 3][1 2][3 5][2 3][4 5][3 4]]
    [[2 4][3 5][1 4][2 3][1 3][4 5][1 2][3 4][2 3]]
    [[2 4][3 5][1 4][2 5][1 3][4 5][1 2][3 4][2 3]]
    [[2 4][3 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]]
    [[2 4][3 5][1 5][2 3][1 3][4 5][1 2][3 4][2 3]]
    [[2 4][3 5][1 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[2 5][3 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[2 5][3 4][1 2][4 5][1 3][2 4][2 3][4 5][3 4]]
    [[2 5][3 4][1 2][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[2 5][3 4][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[2 5][3 4][1 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 5][3 4][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[2 5][3 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]]
    [[2 5][3 4][1 4][2 3][1 3][4 5][1 2][3 4][2 3]]
    [[2 5][3 4][1 4][3 5][1 2][4 5][1 3][2 4][2 3]]
    [[2 5][3 4][1 5][2 3][1 2][3 4][2 3][4 5][3 4]]
    [[2 5][3 4][1 5][2 3][1 3][4 5][1 2][3 4][2 3]]
    [[2 5][3 4][1 5][2 4][1 3][4 5][1 2][3 4][2 3]]


----------


 - 6-input: 90 networks

    [[1 2][3 4][5 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 4][5 6][1 3][2 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 2][3 4][5 6][1 4][2 6][3 5][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 4][5 6][1 5][2 3][4 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 2][3 4][5 6][1 5][2 4][3 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 4][5 6][1 6][2 4][3 5][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 5][4 6][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 5][4 6][1 3][2 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 2][3 5][4 6][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 2][3 5][4 6][1 4][2 5][3 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 5][4 6][1 5][2 6][3 4][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 5][4 6][1 6][2 5][3 4][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 6][4 5][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 6][4 5][1 3][2 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 2][3 6][4 5][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 2][3 6][4 5][1 4][2 6][3 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 6][4 5][1 5][2 6][3 4][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 6][4 5][1 6][2 5][3 4][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 4][5 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 4][5 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 3][2 4][5 6][1 4][2 5][3 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 4][5 6][1 5][2 3][4 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 3][2 4][5 6][1 5][2 6][3 4][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 4][5 6][1 6][2 5][3 4][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 5][4 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 5][4 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 3][2 5][4 6][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 3][2 5][4 6][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 5][4 6][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 5][4 6][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 6][4 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 6][4 5][1 2][3 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 3][2 6][4 5][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 3][2 6][4 5][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 6][4 5][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 6][4 5][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 3][5 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 3][5 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 4][2 3][5 6][1 3][2 5][4 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 4][2 3][5 6][1 5][2 4][3 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 3][5 6][1 5][2 6][3 4][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 3][5 6][1 6][2 5][3 4][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 3][4 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 3][4 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 5][2 3][4 6][1 3][2 4][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 5][2 3][4 6][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 3][4 6][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 3][4 6][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 3][4 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 3][4 5][1 2][3 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 6][2 3][4 5][1 3][2 4][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 6][2 3][4 5][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 3][4 5][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 3][4 5][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]

Лично я бы проверял правильность сортировочной сети перед ее использованием, вместо того, чтобы использовать слово какой-либо случайной страницы в Интернете. Грубая сила "только" требует запустить ее с конечным числом входов: "очевидно" n! входов достаточно, и на самом деле так 2**n (https://en.wikipedia.org/wiki/Sorting_network#Zero-one_principle).

Все оптимальные 5-сети включают "3" в последнем свопе, поэтому выбор медианы за меньшее количество свопов не так-то просто, как все. Однако это можно сделать в 6 сравнениях. Там больше кода, чем вам нужно здесь, если вы можете игнорировать нытье о вопросе:

Код для вычисления "медианы пяти" в С#

Чтобы выбрать медиану, вам необязательно делать какие-либо свопы, кроме, возможно, одного безусловного свопа, если вы хотите сохранить все 5 значений. Движение может быть адекватным.

Ответ 2

Вопрос был специально заинтересован в реализации медианы из 5 на основе сортировочных сетей, поэтому я рассмотрю этот конкретный случай. Краткий обзор литературы показывает, какие оптимальные решения выглядят в соответствии с различными метриками.

Майкл Кодиш, Луис Круз-Филипе, Торстен Элерс, Майк Мюллер и Питер Шнайдер-Камп. "Сортировка сетей: до конца и обратно". Журнал компьютерных и системных наук (2016) в таблице 1 показывает, что при n = 5 минимальное количество сравнений-свопов равно 9, а минимальная глубина сети равна 5. Поскольку каждая сводка сравнения эквивалентна двум минимальным/максимальные операции, минимальное количество минимальных/минимальных операций составляет 18.

Лукаш Секанина, "Эволюционное проектирование космических исследований для медианных цепей". В: EvoWorkshops, март 2004 г., стр. 240-249, дается минимальное количество операций min/max, необходимых для оптимальной сети с пятью входами с медиа-выбором, как 10 в таблице 1.

Уильям Газарх, Уэйн Келли и Уильям Пью. "Нахождение i-го по величине n для малых i, n". ACM SIGACT News 27, no. 2 (1996): 88-96, таблица 1: для медианы 5 требуется не менее 6 сравнений.

В общем случае сортировка сетей с минимальным количеством операций не сводится к сетям медианного выбора с минимальным количеством операций просто путем устранения избыточных операций. Но можно найти сети, которые уменьшают оптимально, по крайней мере, для некоторых значений n. При n = 5 возможен поиск грубой силы для таких сетей.

В приведенном ниже коде показаны четыре варианта сортировочных сетей с пятью входами, включающих 9 операций сравнения или замены, или, в качестве альтернативы, 18 минут/максимальных операций. При компиляции с FULL_SORT = 0 они превращаются в сетки медианного выбора с операциями 10 мин/макс. Таким образом, согласно этой метрике, как сортировка, так и медианный выбор являются оптимальными.

Но при использовании в качестве сортировочной сети все четыре варианта имеют глубину шесть, а не минимум пять. Кроме того, при настройке в качестве сети выбора медиа, основанной на сравнении вместо операций min/max, для всех требуется семь, а не минимум шесть сравнений.

Примеры компиляции из Compiler Explorer (godbolt): использование 18 минут/максимальных операций для пяти входных sort, используя 10 мин/макс. операции для пяти входных медиана.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define VARIANT       1
#define USE_MIN_MAX   1
#define FULL_SORT     0

typedef float T;

#if USE_MIN_MAX
#define MIN(a,b) ((T)(fmin(a,b)))
#define MAX(a,b) ((T)(fmax(a,b)))
#define SWAP(i,j) do { T s = MIN(a##i,a##j); T t = MAX(a##i,a##j); a##i = s; a##j = t; } while (0)
#else // USE_MIN_MAX
#define MIN(a,b) (((a) > (b)) ? (b) : (a))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define SWAP(i,j) do { if (a##i > a##j) { T temp = a##i; a##i = a##j; a##j = temp; }} while (0)
#endif // USE_MIN_MAX

/* Use sorting/median network to fully or partially sort array of five values
   and return the median value
*/
T network5 (T *a)
{
    // copy to scalars
    T a0, a1, a2, a3, a4;
    a0=a[0];a1=a[1];a2=a[2];a3=a[3];a4=a[4];

#if VARIANT == 1
    SWAP (1, 2);  SWAP (4, 3);
    SWAP (2, 3);
    SWAP (0, 2);  SWAP (1, 4);
    SWAP (2, 4);
    SWAP (3, 4);  SWAP (0, 2);
    SWAP (0, 1);
#elif VARIANT == 2
    SWAP (3, 4);  SWAP (0, 2);
    SWAP (2, 4);  SWAP (0, 3);
    SWAP (2, 3);
    SWAP (1, 2);
    SWAP (0, 1);  SWAP (2, 3);
    SWAP (3, 4);
#elif VARIANT == 3
    SWAP (3, 2);  SWAP (0, 4);
    SWAP (2, 4);  SWAP (0, 3);
    SWAP (2, 3);
    SWAP (1, 2);
    SWAP (0, 1);  SWAP (2, 3);
    SWAP (3, 4);
#elif VARIANT == 4 
    SWAP (2, 4);  SWAP (0, 1);
    SWAP (0, 2);  SWAP (1, 4);
    SWAP (2, 3);
    SWAP (1, 2);
    SWAP (2, 3);  SWAP (0, 1);
    SWAP (3, 4);
#else
#error unsupported VARIANT
#endif

#if FULL_SORT
    // copy back sorted results
    a[0]=a0;a[1]=a1;a[2]=a2;a[3]=a3;a[4]=a4;
#endif
    // return median-of-5
    return a2;
}