挿入ソート - アルゴリズムにALGOS

Question

にMITイントロを読んトラブルMITイントロソートなどの挿入について説明します。

を私のようにPythonでこれを書いた：

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

     # i > 0 should be i >= 0 
     while i > 0 and A[i] > key: 
      A[i + 1] = A[i] 
      i = i - 1; 
     A[i + 1] = key 

    return A 

しかしラインwhile i > 0紹介最初の2つのキーが間違った位置にあります。これをwhile i >= 0に変更すると、この問題が修正されます。

なぜこれはMITイントロの書籍に含まれていませんか？それを間違って読んでいますか？

Answer 1

本書のアルゴリズムは1からA.lengthまでのインデックス付けを想定しているため、インデックス2から開始されます。Pythonの配列インデックスは0からlen(A) - 1までです。 rangeでそれを修正しましたが、あなたはループテストでそれを修正することを怠りました。そうすることで、問題が解決されます。

Answer 2

@pjsが正確です。 1ベースの配列のために書かれたアルゴリズムを0以外のものがない0ベースのアルゴリズムに変換するための方法論的な方法を、各配列参照で1を減算してから代数を使う以外は、簡略化する。ここでは、で終わるだろう：それはゼロを追加していますので、

もちろん

def sort(A): 
    for j in range(2, len(A) + 1): # +1 is because Python ranges exclude high limit 
    key = A[j - 1] 
    i = j - 1 
    while i > 0 and A[i - 1] > key: 
     A[i + 1 - 1] = A[i - 1] 
     i = i - 1 
    A[i + 1 - 1] = key 
    return A 

それは、+ 1 - 1を除去することにより、簡素化するのは簡単です！結果は正常に動作します。

あなたは、1よりもむしろ2から始まる、外側範囲とコードがきれいにする（両側に1を加算）置換jj = j - 1を作りたい場合はj = jj + 1を意味する：

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj + 1 - 1] 
    i = jj + 1 - 1 
    while i > 0 and A[i - 1] > key: 
     A[i] = A[i - 1] 
     i = i - 1 
    A[i] = key 
    return A 

再び+ 1 - 1 Sを除去します、we have

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    i = jj 
    while i > 0 and A[i - 1] > key: 
     A[i] = A[i - 1] 
     i = i - 1 
    A[i] = key 
    return A 

これはすばらしく、私はここでやります。しかし、もう1つのバリエーションは置換ii = i - 1またはi = ii + 1で可能です。

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    ii + 1 = jj 
    while ii + 1 > 0 and A[ii + 1 - 1] > key: 
     A[ii + 1] = A[ii + 1 - 1] 
     ii + 1 = ii + 1 - 1 
    A[ii + 1] = key 
    return A 

hmmm ... iiへの割り当ては奇妙に見えます。しかし、代数を使ってすべてを整えることができます。

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    ii = jj - 1 # Subtracted 1 from both sides 
    while ii >= 0 and A[ii] > key: # x + 1 > 0 iff x >= 0 
     A[ii + 1] = A[ii] 
     ii = ii - 1 # Subtracted 1 from both sides and simplified 
    A[ii + 1] = key 
    return A 

あなたが提案したコードがあります。毎回動作します。