Стандартные сортировочные сети для малых значений n
Я ищу реализацию сети сортировки с 5 элементами, но так как я не смог найти хорошую ссылку на SO, я хотел бы попросить сети сортировки для всех небольших значений n, по крайней мере, n=3 через n=6, но более высокие значения также были бы хорошими. Хороший ответ должен по крайней мере перечислять их как последовательности операций "подкачки" (сортировки по 2 элементам), но было бы также неплохо увидеть рекурсивное разложение в терминах сетей сортировки более низкого порядка.
Для моего приложения я на самом деле забочусь только о медиане из 5 элементов, а не о том, чтобы привести их в порядок. Таким образом, порядок других 4 элементов может быть неопределенным в результате, пока медиана окажется в нужном месте. Можно ли использовать подход, связанный с сетями сортировки, для вычисления медианы с меньшим количеством свопов, чем для выполнения полной сортировки? Если это так, то такое решение моей проблемы (для n=5) и для других случаев также будет отличным ответом.
(Примечание: я пометил этот вопрос C, потому что C - это язык, который я использую, и я подозреваю, что люди, которые следуют за тэгом C, имеют хорошие ответы, но мне все равно, действительно ли ответ написан на C, а не на псевдокоде, как при условии, что он легко переводится в C, что, естественно, следует делать при условии соблюдения вышеупомянутых критериев.)
3 ответа
Выберите по одному в каждом разделе, предположительно, в зависимости от того, что работает быстрее всего на вашем оборудовании, поскольку мы твердо находимся в области "чудовищной оптимизации": http://smarterrecall.com/networks.html, воспроизведенной ниже:
Я создал этот сайт, чтобы перечислить все возможные оптимальные сети сортировки до 6 входов, написанные с использованием программы в Matlab. Самое длинное время работы для 5 входов при 45 секундах. Если вы заинтересованы в том, чтобы связаться со мной, со мной можно связаться по адресу rpl1 [AT] rice [DOT] edu Cheers, Richard L.
----------
- 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).
Все 5 оптимальных сетей включают "3" в последнем обмене, поэтому выбор медианы за меньшее количество обменов не так прост, как все это. Это можно сделать за 6 сравнений. Здесь гораздо больше кода, чем вам нужно, если вы можете игнорировать нытье по поводу вопроса:
Код для вычисления "медианы пяти" в C#
Чтобы выбрать медиану, вам не обязательно делать какие-либо свопы, кроме, возможно, одного безусловного свопа, если вы хотите сохранить все 5 значений. Движение может быть адекватным.
Аскер был особенно заинтересован в реализации медианы 5, основанной на сортировке сетей, поэтому я рассмотрю этот конкретный случай. Краткий обзор литературы показывает, как выглядят оптимальные решения в соответствии с различными показателями.
Майкл Кодиш, Луис Круз-Филипе, Торстен Элерс, Майк Мюллер и Питер Шнайдер-Камп. "Сортировка сетей: до конца и обратно". Журнал Computer and System Sciences (2016) в таблице 1 показывает, что для n = 5 минимальное количество обменов подкачки равно 9, а минимальная глубина сети -5. Поскольку каждый обмен подкачки эквивалентен двум мин / максимальное количество операций, минимальное количество требуемых минимальных / максимальных операций составляет 18.
Лукаш Секанина, "Эволюционный проект освоения космоса для срединных цепей". В: EvoWorkshops, март 2004 г., стр. 240-249, приведено минимальное количество операций min/max, необходимых для оптимальной сети с медианой выбора из пяти входов, равное 10 в таблице 1.
Уильям Гасарч, Уэйн Келли и Уильям Пью. "Нахождение i-го по величине из n для малого i, n." ACM SIGACT Новости 27, нет. 2 (1996): 88-96, таблица 1: по крайней мере 6 сравнений необходимы для медианы-5.
В общем, сети сортировки с минимальным количеством операций не сводятся к сетям с медианным выбором с минимальным количеством операций просто за счет исключения избыточных операций. Но можно найти сети, которые оптимально уменьшаются, по крайней мере, для некоторых значений n. При n = 5 возможен поиск таких сетей методом "грубой силы".
Приведенный ниже код показывает четыре варианта сетей сортировки с пятью входами, включающих девять операций сравнения-обмена или, альтернативно, 18 минут / макс. Когда скомпилировано с FULL_SORT = 0 они превращаются в сети с медианным отбором с 10 мин / макс операциями. Таким образом, согласно этой метрике, сортировка и выбор медианы являются оптимальными.
Однако при использовании в качестве сортировочной сети все четыре варианта имеют глубину шесть, а не минимум пять. Кроме того, когда конфигурируется как сеть с медианным выбором на основе сравнений вместо операций min/max, для всех требуется семь, а не минимум шесть сравнений.
Пример результатов компиляции из Compiler Explorer (godbolt): использование 18 мин / макс операций для сортировки с пятью входами, использование 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 (0, 1); SWAP (2, 3);
SWAP (0, 2); SWAP (1, 3);
SWAP (2, 1);
SWAP (1, 4);
SWAP (1, 2);
SWAP (0, 1); SWAP (3, 4);
#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;
}
Слишком долго для комментария. Приведенный выше ответ профессора Фалькена может быть проверен в MATLAB по следующим направлениям: с помощью небольшого количества поиска / замены или регулярного выражения, напишите
sn{3} = [...
[[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]];
];
и аналогично для других значений n, затем запустите
for n = 3:6
test_in = cellfun(@str2num,num2cell(dec2bin(0:(2^n-1),n)));
for j = 1:size(sn{n},1)
test_out = test_in;
for k = 1:2:size(sn{n},2)
temp1 = test_out(:,sn{n}(j,k));
temp2 = test_out(:,sn{n}(j,k+1));
ind = temp2 < temp1;
test_out(ind,sn{n}(j,k)) = temp2(ind);
test_out(ind,sn{n}(j,k+1)) = temp1(ind);
end
end
test = cellfun(@issorted,mat2cell(test_out,ones(1,2^n),n));
assert(all(test),['n = ',num2str(n),' failed test']);
end
Утверждения верны для каждого значения n.