삽입 정렬 알고리즘의 종결 루프에서 j = n + 1이 왜 불규칙합니까?

Question

현재 TCRC Introduction to Algorithms 제 3 판 교과서 2 장을 읽고 있는데이 알고리즘의 루프 불변성에 대한 저자의 해석을 읽었습니다. 초기화와 유지 보수에 대한 저자의 논리를 이해합니다. 그러나, 종결은 내가 꽁꽁 얼어 붙은 것입니다. 저자는 종료시에 j = n + 1이라고 주장합니다. 그러나 알고리즘의 의사 코드에서 j는 2에서 n으로 반복됩니다. 그러니 j = n - 1일까요?

편집 : 일종의 삽입이 책의 의사 코드 :

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 

편집 :주의 깊게 읽은 후, 나는 마침내 종료하는 동안 왜 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 루프 외부에 정의되어 있으며 루프가 종료 될 때 최종 값을 갖습니다. 그것은 포함 또는 A.length 제외됩니다 A[j]

모호성이 for j = 2 to A.length에 단어 to로 존재합니다는 코드가 인덱서로 j를 사용하여 배열을 목표로, Dukeling의 코멘트 @

둘째를 참조? 및 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]의 유효한 범위가 있습니다.

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

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