代码之家  ›  专栏  ›  技术社区  ›  R.. GitHub STOP HELPING ICE

小n值的标准排序网络

sorting-network median sorting c
  •  13
  • R.. GitHub STOP HELPING ICE  · 技术社区  · 15 年前

    (注意:我标记这个问题C是因为C是我使用的语言,我怀疑遵循C标记的人有很好的答案,但我并不真的在乎答案是用C还是伪代码写的,只要它很容易翻译成C,只要满足上述条件,它自然会这样做。)

    3 回复  |  直到 10 年前
        1
  •  16
  •   Prof. Falken    8 年前

    从每个部分中选择一个,大概是在您的硬件上运行最快的部分,因为我们坚定地处于“恶魔优化”的领域: http://smarterrecall.com/networks.html ,转载如下:

    我创建这个网站是为了列出所有可能的最佳排序网络,最多6个输入,使用matlab中的程序编写。最长的运行时间是45秒5个输入。如果你有兴趣与我联系,我可以在rpl1[at]rice[DOT]edu联系 理查德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#Zero-one_principle

    所有最优的5-网络在最后一次交换中都包含“3”,因此在更少的交换中选择中间值并不像所有这些那么容易。不过,这可以通过6个比较来完成。如果你可以忽略对这个问题的抱怨,这里的代码比你需要的要多得多:

    Code to calculate "median of five" in C#

    任何 交换,如果您希望保留所有5个值,则可能不是一个无条件交换。一个举动也许就足够了。

        2
  •  2
  •   njuffa    7 年前

    迈克尔·科迪什、卢斯·克鲁斯·菲利佩、托尔斯滕·埃勒斯、迈克·姆勒和彼得·施奈德·坎普。”对网络进行排序:到最后再返回。” 计算机与系统科学杂志 n个 =5,比较交换的最小数目为9,网络的最小深度为5。由于每个比较交换相当于两个最小/最大操作, 所需的最小/最大操作数最少为18。

    Luk Sekanina,“中值电路的进化设计空间探索”。在: ,2004年3月,第240-249页,给出了表1中5输入中值选择网络所需的最小/最大操作数为10。

    威廉·加斯克、韦恩·凯利和威廉·普赫。”找到n中的第i个大数表示小i,n ACM SIGACT新闻 27,第2号(1996):88-96,表1: 至少需要6次比较才能得到5的中位数。

    不 n个 . 为了 n个 =5,对此类网络进行暴力搜索是可行的。

    FULL_SORT = 0 这些网络将转变为具有10分钟/最大操作的中值选择网络。所以根据这个指标,排序和中值选择都是最优的。

    但是,当用作排序网络时,所有四个变体的深度都是6,而不是最小的5。此外,当配置为基于比较而不是最小/最大操作的中值选择网络时,所有这些都需要7个而不是最小的6个比较。

    编译器资源管理器(godbolt)的编译结果示例:对五个输入使用18 min/max操作 sort median . 

    #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;
}
        3
  •  1
  •   S Huntsman    8 年前

    太长,无法评论。上面Falken教授的答案可以在MATLAB中按照以下几行进行验证:使用find/replacing或regex fu,编写 

    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

    推荐文章
    Aidan  ·  为什么在将最后一个索引分配给空终止符(\0)后,我无法释放char缓冲区
    1 年前
    Chris  ·  用目的地捕捉信号
    1 年前
    MaPo  ·  Linux,设置锁定ICMP_过滤器选项
    1 年前
    KevInSol  ·  在FreeBSD的配置阶段,从源代码构建PHP时找不到libjpeg
    1 年前
    Doohyeon Won  ·  内联函数上的奇怪现象?[关闭]
    1 年前
    MaSc. H.  ·  大小与阵列大小
    1 年前
    Fulmineo  ·  我的C代码运行良好,但在结束前崩溃(0xC0000374)
    1 年前
    Mehan Alavi  ·  TCP Socket-打印字符串中所有不在C中的字符不起作用
    1 年前
    Bobby  ·  复合字面值总是左值吗?
    1 年前
    9-Pin  ·  C: 嵌套结构的堆栈内存分配
    1 年前
    关于   移动版
    代码之家 - 一站式码农服务社区
    沪ICP备11025650号