0

CLRS で Insertion Sort アルゴを使用していました。どちらが正しい実装かわかりません -

CLRS からのアルゴリズム - CLRS 疑似コード

実装 1 :

def Insertion_sort():
list = [3,5,1,7,2,4]
for j in xrange(1,len(list)):
    i = j-1
    while i>=0 and list[i] > list[j]:
        swap(list, i, j)
        j = i
        i = i-1

実装 2:

def Insertion_sort2():
list = [3,5,1,7,2,4]
for j in range(1,len(list)):
    i = j-1;
    while i>=0 and list[i]>list[j]:
        i = i-1;
    swap(list, i+1, j)

ありがとう

4

2 に答える 2

0

提案された関数はどちらも、実際には CLRS で提示されているアルゴリズムを再現していません。

CLRS アルゴリズムの 5 行目から 8 行目のコードは、index で終わるリストのサブシーケンスのローテーションjを行います。jこれにより、インデックスの値がリストのプレフィックスの正しい位置に挿入されます。

最初の関数は同じことを行いますが、ローテーションを行う代わりに一連のスワップを行います。ローテーションは、各リスト項目を 2 回ではなく 1 回だけ変更するため、はるかに効率的です。

2 番目の関数は、要素の値を適切な場所に移動する単一のスワップを行うだけですがj、リストの残りのプレフィックスの順序は保持しません。したがって、はるかに高速ですが、誤った結果が生成されます。(たまたまテスト ベクトルで並べ替えられた出力が生成されたという事実は面白いですが、各挿入ポイントで連続するプレフィックスを見ると、実際には機能していないことがわかります。[2, 3, 1]たとえば、並べ替えを試してみてください。 )

于 2016-01-22T02:02:13.340 に答える
-1

どちらも正しく、両方とも O(n^2) 時間で実行されますが、最初の実装では O(n^2) スワップを行うのに対し、リストの各要素に対して 1 回のスワップしか行わないため、2 番目の実装の方が優れています。最初の実装では、数字が正しい位置になるまで、場違いな数字を次の数字と交換しますが、2 番目の実装では、数字を最終的な正しい位置に入れ替える前に、場違いな数字の正しいインデックスを見つけます。スワップは O(1) 時間ですが、単純に数値を減らすよりも時間がかかります。

于 2016-01-20T07:54:07.067 に答える