Insertion_Sort（）実装（エラー）、Python

Question

私はINSERTION SORTの実装の2つのバージョンを持っています。私はと同等だと思うが、だが、は、ソートされたリストを間違って返す。 これは最初のものである：

def insertionSort(A): 
for j in range(1,len(A)): 

    key = A[j] 
    i = j 

    while i>0 and A[i-1]>key: 
     A[i] = A[i-1] 
     i -= 1 

    A[i] = key 

これが二番目である。

def insertionSort(A): 
    for j in range(1,len(A)): 

     key = A[j] 
     i = j-1 

     while i>0 and A[i]>key: 
      A[i+1] = A[i] 
      i -= 1 

     A[i+1] = key 

Iは最初のケースで

C = [54,26,93,17,77,31,44,55,20] 
insertionSort(C) 
print(C) 

このCアレイとこれら二つのアルゴリズムをテストしてみました私の配列は正しくソートされています。第二の場合には私の結果は：

[54、17、20、26、31、44、55、77、93]

第二ケースは私の学校に擬似コードから来ています本。 なぜ正しく動作しないのですか？

Answer 1

はここで2番目のコードの修正です：

def insertionSort(A): 
    for j in range(1,len(A)): 

     key = A[j] 
     i = j-1 

     while i>=0 and A[i]>key: 
      A[i+1] = A[i] 
      i -= 1 

     A[i+1] = key 

違いは、whileループで>に向けて>=です。 理解するには、挿入ソートの動作を参照してください。 そのソートアルゴリズムでは、配列[0、j-1]がソートされていることを前提とし、要素を正しい場所に配置します。

今、私たちは[4,3,2,0,5,6,7]をソートするwan't、我々はその状態で、今だと仮定することができます：

A = [2, 3, 4, 0, 5,6,7] 

最初の3つの要素が適切な場所にあり、我々はその右に0を配置する必要があり位置（インデックス0）。 i = 2からi = 0までの間、条件A[i] > keyは常に真です。したがって、A [3] = A [2]、A [2] = A [1]、A [1] = A [0]を実行します。

次にループをi = -1とし、A[i+1] = A[0] = 0とします。

以前のバージョンでは、ループはi = 0で終了し、最後の命令はA[0+1] = A[1] = 0になります。アルゴリズムで[2, 3, 4, 0, 5,6,7]を指定すると、結果が悪くなります。