0

ある種のスマートソートアルゴリズムがあるかどうか（確かにそうですが、何を探すべきかわかりません）に興味があります。

スマート ソート アルゴリズムとはどういう意味ですか? 例を考えてみましょう：

私はソートされたテーブルに5つの数字を持っています:

1, 2, 3, 4, 5

次に、2 番目と 4 番目を入れ替えると、次のようになります。

1, 4, 3, 2, 5

2 番目のステップとして、5 番目と 2 番目を交換するので、最終結果は次のようになります。

1, 5, 3, 2, 4

アルゴリズムについての私の期待は、最終セットを入力 (1、5、3、2、4) として配置することです。その結果、2 番目と 5 番目のアイテムを交換し、次に 2 番目と 4 番目を交換する必要があるという情報を取得したいと考えています。ソートされたリスト。

私はソートネットワークの使用について考えていました.特定のサイズのデータ​​に対して必要なすべての比較とスワップ命令を生成し、入力データに対して行われるスワップを返すことができましたが、他の方法があるのでしょうか?

何を探すべきですか？

4

2 に答える 2

2

スワップの最小数を見つけることは、通常、並べ替えには重要ではありません (スワップはポインターで行うことができます) が、それ自体はよく知られた問題です。

この質問を見てください: ある順列を別の順列に変換するために必要な隣接スワップのカウント

または、あなたの研究をEdit Distanceに向けてください。

于 2013-08-31T11:20:13.600 に答える
1

ここでの問題は、実際のデータの交換には非常にコストがかかることですが、比較すると比較的安価です。

まず、通常の並べ替えアルゴリズムを使用して、配列内の各要素の位置を見つけます。それを行うためのアルゴリズムはたくさんあります。たとえば、クイックソートや単なるバブルソート、挿入ソートなどです。

これで、各要素がどこに行くべきかがわかったので、ここから元のデータをソートされた位置に移動するための最適な一連のスワップを見つけることができます。

擬似コードの例:

compare(proxy1, proxy2)
  return compare(proxy1.data, proxy2.data)

smartSort(unsorted)
  swaps = []
  count = size(unsorted)
  // create a proxy for all elements
  proxiesOrig = [ new proxy(data) | for unsorted as data ]
  // and make a copy which we are going to sort
  proxiesSort = shallowCopy(proxiesOrig)
  sort(proxiesOrig)  // Do a regular sort here, using the compare function above
  // now note the location of each target
  // because we made a shallow copy, the location will also be marked in the
  // proxiesOrig list
  for i = 1 .. count
    proxiesSort[i].location = i
  // Now the proxiesOrig is the unsorted list
  // with location information to where everything needs to go
  for i = 1 .. count
    while (proxiesOrig[i].location <> i)
      // swap the proxy on location i with the one to where i needs to go
      swap(proxiesOrig, i, proxiesOrig[i].location)
      // and record it
      swaps.add(i, proxiesOrig[i].location)
  return swaps
于 2013-08-31T11:19:19.690 に答える