単純な挿入でのロジックインパース

Question

私は自分自身にPythonを教えているし、比較的単純なコンセプトでは難しかった。目標は、挿入ソートを使用して昇順にソートすることです。コードは次のとおりです。

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] # this is the not understood point 
      i = i - 1 
     A[i+1] = key 
    print A 

太字のステップがどのように機能するかわかりません。例えば、私が[6,5,4,3,1]のリストを持っていて、2番目の繰り返しになった場合、私のリストは[6,6,4,3,1]になりませんか？私はA [i]（最初のケースでは5となる）A [i]（最初のケースでは6）の値をA [i + 1]に割り当てます。私の5に何が起こったのですか？コードでの私の最初の試みは：

def InsertionSort(A): 
    for j in range(1, len(A)): 
     key = A[j] 
     i = j - 1 
     while (i >=0) and (A[i] > key): 
      temp = A[i+1] 
      A [i+1] = A[i] 
      A[i] = temp 
      i = i - 1 
     A[i+1] = key 
    print A 

この方法も有効でした。私はなぜ最初のものも同様に理解していない。誰でも刺すようにしたいですか？

Answer 1

あなたは[6,5,4,3,1]で始まる場合は、次のように反復は次のようになります。

第1工程：

[6,5,4,3,1] 
    ## first number sorted` 

第二段階（j=2）：

key <- 5 

A <- [6,6,4,3,1], i <- -1 
    ## the 5 will be overridden but is still save in the key variable 

A <- [5,6,4,3,1]   
    ## A[i+1] = key will restore the 5 

値のみ取得することができます」 「失われた」はA[j]に含まれるものです。しかし、この値は常に変数keyに保存されるため、最後のステップで復元することができます。

Answer 2

私はそれが単にA[i+1]=keyという行のためだと思います。 、つまりリスト要素3を考慮しているとします。リスト[1,2,4,5,3]を考えてみましょう。 algorighmはkeyの要素3を格納し、次のチェック：各反復において上記とは対照的に

[1,2,4,5,3] 
    ^ 5>3 (key) => move 5 forward by 1 => [1,2,4,5,5] 
[1,2,4,5,5] 
    ^ 4>3 (key) => move 4 forward by 1 => [1,2,4,4,5] 
[1,2,4,4,5] 
^  2<3 => stop inner while loop 
now, make A[i+1]=key (remember: key is 3): 
[1,2,3,4,5] 

、第2のアルゴリズムは、実際スワップ要素：アルゴリズムの

[1,2,4,5,3] 
    ^ 5>3 (key) => swap 5 and 3 => [1,2,4,3,5] 
[1,2,4,3,5] 
    ^ 4>3 (key) => swap 4 and 3 => [1,2,3,4,5] 
[1,2,3,4,5] 
^  2<3 => stop while loop 
now, make A[i+1]=key (remember: key is 3): (this is unnecessary!) 
[1,2,3,4,5]