1

Python で次の疑似コードを実装しようとしています (挿入ソートのロシアのページから):

for i = 2, 3, ..., n:  
    key := A[i]
    j := i - 1
    while j >= 1 and A[j] > key:
        A[j+1] := A[j]
        j := j - 1
    A[j+1] := key

エラーがあります: Traceback (most recent call last): File "insertion.py", line 6, in test_sort self.assertEqual( sort( [ 5, 2, 6, 3, 7 ] ), [ 2, 3, 5 , 6, 7 ] ) ファイル "insertion.py"、12 行目、ソート キー = a[ i ] IndexError: リスト インデックスが範囲外です

sort() の私のコードは次のとおりです。

def sort( a ):
    len_a = len( a )
    len_a_plus_1 = len_a + 1
    for i in range( 2, len_a_plus_1 ):
        key = a[ i ]
        j = i - 1

        while j >= 1 and a[ j ] > key:
            a[ j + 1 ] = a[ j ]
            j -= 1
        a[ j + 1 ] = key

    return a

range() 呼び出しの引数を変更すると:

for i in range( 2, len_a )

...その後、間違った結果が得られます:

[5, 2, 3, 6, 7]

私のコードは間違っていますか、それとも記事のアルゴリズムが不正確ですか?

更新します。

コードを変更しました (0-indexed Python 原則を使用) が、正しく動作しません:

def sort( a ):
    len_a = len( a )
    for i in range( 1, len_a ):
        key = a[ i ]
        j = i - 1

        while j and a[ j ] > key:
            a[ j + 1 ] = a[ j ]
            j -= 1
        a[ j + 1 ] = key

    return a

入力: [ 5, 2, 6, 3, 7 ] 出力: [5, 2, 3, 6, 7]

解像度。

解決策を見つけました：

while j and a[ j ] > key

あるべき

while j >= 0 and a[ j ] > key
4

2 に答える 2

4

[5, 2]どちらも機能しません。チェックするだけwhile j (>0)では、最初のアイテムを移動することはありません。これはうまくいくと思います

while j >= 0 and a[ j ] > key:
于 2013-07-04T08:23:13.577 に答える
2

Python は 0 ベースのインデックスを使用a[len(a)]し、範囲外にします。疑似コードは、1 から始まるインデックスを使用します。

両方のインデックスを 1減らす必要があります。

len_a = len(a)
for i in range(1, len_a):

と

while j >= 0 and a[j] > key:
于 2013-07-04T08:04:05.407 に答える