Question

I am reading Introduction To Algorithms book and the pseudo code is

INSERTION-SORT(A)
1 for j ← 2 to length[A]
2   do key ← A[j]
3     ▹ Insert A[j] into the sorted sequence A[1  j - 1].
4     i ← j - 1
5     while i > 0 and A[i] > key
6      do A[i + 1] ← A[i]
7         i ← i - 1
8     A[i + 1] ← key

While the pseudo code on wiki is

 for j ←1 to length(A)-1
     key ← A[ j ]
     > A[ j ] is added in the sorted sequence A[0, .. j-1]
     i ← j - 1
     while i >= 0 and A [ i ] > key
         A[ i +1 ] ← A[ i ]
         i ← i -1
     A [i +1] ← key

Why does one start with 2 and loops up to length and the other starts with 1 and loops until length of A -1?

Was it helpful?

Solution

It looks like the first pseudocode block used 1 based indexing while the second uses 0 based indexing.

OTHER TIPS

It's basically the same thing, just that one's index starts at 0 (zero-based) and the other's at 1 (one-based). E.g. in C#'s arrays are zero-based, while VB's are one-based.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top