挿入ソートアルゴリズムの不変の終了ループでj = n + 1となるのはなぜですか？

Question

私は現在TCRC Introduction to Algorithms第3版の教科書の第2章を読んでおり、私はこのアルゴリズムのループ不変量の著者の解釈を読んでいます。私は初期化とメンテナンスの両方について著者の論理を理解しています。しかし、終結は、私がうんざりしているものです。著者は終了時に、j = n + 1と主張する。しかし、アルゴリズムの擬似コードでは、jは2からnまでループする。だから、j = n - 1ではないはずですか？

EDIT：挿入のための本の擬似コードソートされます。

for j = 2 to A.length 
    key = A[j] 
    // Insert A[j] into sorted sequence A[1...j - 1] 
    i = j - 1 
    while i > 0 and A[i] > key 
     A[i + 1] = A[i] 
     i = i - 1 
    A[i + 1] = key 

EDIT：慎重にそれを読んだ後、私は終了時に、なぜJ = N + 1をようやく理解しています。これはforループが2からn（包括的に）になるためです。したがって、jがnを超えた後にループが終了し、終了時にj = n + 1となる理由です。私は助けに感謝します。

Answer 1

免責事項：これは完全に間違っている可能性があります...それはちょうど脳の唾です。

サイドノート：このループ中にjがインクリメントされるため、開始点は終了条件とは無関係です。

for j = 2 to A.length //A.length = n in your question 

この疑似コードには多少の曖昧さがあります。

最初に、jはこのforループの外側で定義され、ループが終了すると終了値を持つと仮定します。がDukelingさんのコメント

第二に、@見、あなたのコードは、インデクサとしてjを使用して、配列を標的にされていますA[j]

曖昧さは、それが含むかA.length除くされ、for j = 2 to A.lengthに単語toに存在しますか？このインデクサA[j]

は、一般的なケースであり、A[j]でインデクサため、jの有効な範囲は[0...A.length -1]

あるいくつかの言語、すなわち別の範囲、使用しています：[1...A.length]を私がするので、これは作者が意図していると思うA[0]全くヒットしていない。それは（条件をテストし、それが虚偽であることを確認するために）ループを壊す前に

その場合は....とfor条件刻みjは、それから...あなたはj = A.length + 1を取得します。サイドノートとして

：言語のような一般的なCで

、配列は[0...A.length -1]から有効範囲を持っています。

そして、このCの例では、cが終了した後A.lengthの値を持っています

int c = 0; 
for (c = 3; c < A.length; c++) 
{ 

} 
//c = A.length after the loop is completed.