CODEWITHSUNDEEP
algorithmpseudocodeinsertion-sort
CodeCrack
CodeCrack

Reputation: 5363

Insertion sort - pseudocode 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?

Upvotes: 0

Views: 6127

Answers (2)

Bobzit
Bobzit

Reputation: 1

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.

Upvotes: 0

John Percival Hackworth
John Percival Hackworth

Reputation: 11531

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

Upvotes: 7

Related Questions