3

長さ 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 要素リストのすべての順列をテストできました。もっと速い方法はありますか？また、あるとすれば、それは何ですか? それはなんと呼ばれていますか？それはおそらく最速のソリューションですか？

4

1 に答える 1

9

あなたが説明しているのは、ソーティングネットワークと呼ばれるアルゴリズムです。残念ながら、一連のスワップが有効な並べ替えネットワークを生成するかどうかを判断する問題はco-NP-completeであることが知られています。つまり、P = NP でない限り、特定のペアの選択が正しく機能するかどうかを確認するための多項式時間アルゴリズムは存在しません。 .

ただし、興味深いことに、入力のすべての可能な順列を試す必要はありません。ソート ネットワークが 0 と 1 のリストを正しくソートする限り、入力シーケンスを正しくソートするという、ゼロ 1 の原則と呼ばれる結果があります。したがって、すべての n! を試すのではなく、入力の可能な順列、0 と 1 の2 n 個の可能なシーケンスすべてをチェックできます。n が非常に大きい場合、これはまだかなり実行不可能ですが、選択した n が小さい場合には役立つ可能性があります。

仕分けネットワークを構築する最善の方法については、未解決の問題です。ほとんどの入力で高速に実行される優れた並べ替えネットワークが多数あり、最適であることが知られている並べ替えネットワークもいくつかあります。「最適な並べ替えネットワーク」を検索すると、役立つリンクが表示される場合があります。

お役に立てれば！

于 2013-05-13T16:45:12.480 に答える