确定比较和交换指令列表是否将对长度为N的列表进行排序

Question

假设我有一个长度为N的数组中的索引对列表.我想确定在执行后是否对任意排序的列表进行排序

for pair in pairs:
  if list_to_sort[pair.first] > list_to_sort[pair.second]:
    swap(
      element_a_index=pair.first,
      element_b_index=pair.second,
      list=list_to_sort
    )

显然,我可以测试N元素列表的所有排列.有更快的方法吗？如果有,那是什么？这叫什么？它可证明是最快的解决方案吗？

Answer 1

您所描述的是一种称为排序网络的算法.不幸的是,众所周知,确定一系列交换是否产生有效排序网络的问题是共同NP完全的,这意味着除非P = NP,否则没有多项式时间算法来检查您的特定选择对是否能正常工作.

有趣的是,您不需要尝试所有可能的输入排列.有一个称为零一原则的结果表明,只要您的排序网络将正确排序0和1的列表,它将正确排序任何输入序列.因此,而不是尝试所有n!输入的可能排列,您可以检查0和1的所有2 ^n个可能序列.如果n非常大,这仍然是不可行的,但如果您选择的n很小,则可能有用.

至于建立分拣网络的最佳方式 - 这是一个悬而未决的问题!有许多良好的分拣网络可以在大多数输入上快速运行,并且还有一些已知最佳的分拣网络.搜索"最佳排序网络"可能会发现一些有用的链接.

希望这可以帮助!