pseudocode - Can't get insertion sort from introduction to algorithms 3rd ed. right. Where is my thinking mistake? -

i working way through book introduction algorithms, 3rd edition. 1 of first things explained insertion sort. on page 18 there pseudo code:

a = { 5, 2, 4, 6, 1, 3 };

insertion-sort(a) 1 j = 2 a.length 2   key = a[j] 4   = j - 1  5   while (i > 0 , a[i] > key) 6     a[i + 1] = a[i] 7     = - 1  8   a[i + 1] = key 

it says pseudo code used translated kind of language (c, c++, java, don't mention, guess c# too). since program in c#, translated in linqpad.

int[] = { 5, 2, 4, 6, 1, 3 };  (var j = 1; j < a.length; j++) {     var key = a[j];      var = j - 1;      while(i > 0 && a[i] > key)     {         a[i + 1] = a[i];         i--;     }      a[i + 1] = key; }  a.dump(); 

you're going ask, why j start @ 1, when says 2? in book, array has index starting @ 1. , yes, should have updated [i - 1] , [i + i] well.

anyways, after done, run code , notice doesn't sort correctly. output { 5, 1, 2, 3, 4, 6 }. late , should have stopped, struggled on make code correct. did everything, taking pseudo code book (starting @ 2). still not correct output.

i contacted 1 of professors of book, , send me code insertion sort, in c:

void insertion_sort(int *a, int n) {   (int j = 2; j <= n; j++) {     int key = a[j];     int = j-1;      while (i > 0 && a[i] > key) {       a[i+1] = a[i];       i--;     }      a[i+1] = key;   } } 

translated in c#:

int[] = { 5, 2, 4, 6, 1, 3 };

for (var j = 2; j <= a.length; j++) {     var key = a[j];      var = j - 1;      while(i > 0 && a[i] > key)     {         a[i + 1] = a[i];         i--;     }      a[i + 1] = key; } 

i array out of bounds. okay maybe:

int[] = { 5, 2, 4, 6, 1, 3 };

for (var j = 2; j <= a.length - 1; j++) {     var key = a[j];      var = j - 1;      while(i > 0 && a[i] > key)     {         a[i + 1] = a[i];         i--;     }      a[i + 1] = key; } 

output: { 5, 1, 2, 3, 4, 6 }

i'm thinking, can't correct. pseudo code says 2 array.length. 2 < array.length, or 2 <= array.length? going on here?

i think because of 0 > 0 predicate in while loop. falls short 1 time each time.

my explanation (from email sent professor, lazy type over):

the reason why loop still ends { 5, 1, 2, 3, 4, 6 } because of i > 0 predicate. every time in while loop subtract 1 of (i--). lead 0 > 0 ends false (only 0 == 0 return true), when loop still needs run 1 more time. continuously falls 1 short. should go while loop 1 more time sort.

another explanation:

when j starts 2, key == 4, == 1 , a[i] == 2. while loop won't run in case because 2 > 0 2 isn't greater 4.

j == 3, key == 6, == 2, a[i] == 4

while loop won't run because 4 not greater 6

j == 4, key == 1, == 3, a[i] == 6

while loop runs time:

a[i + 1] = a[i] -> a[4] = a[3] -> { 5, 2, 4, 6, 6, 3 } i-- -> == 2

again while loop because 2 > 0 , 4 > 1

a[i + 1] = a[i] -> a[3] = a[2] -> { 5, 2, 4, 4, 6, 3 } i-- -> == 1

again while loop because 1 > 0 , 2 > 1

a[i + 1] = a[i] -> a[2] = a[1] -> { 5, 2, 2, 4, 6, 3 } i-- -> == 0

and here goes (in opinion) wrong. equal zero, while loop should run 1 more time 5 out of zero-th position.

the professor assures me correct, can't right output. thinking going wrong?

---

the array in c code got sent me professor starting index of 1. did not know , checking upon c arrays saw start 0. yes, c code doesn't produce correct output. professor explained me , pieces fall place.

i think prof using 1-based array notation, while (i > 0 && a[i] > key), missing a[0] element in loop. change initial code works:

for (var j = 1; j < a.length; j++) {     var key = a[j];      var = j - 1;      while(i >= 0 && a[i] > key)  <----------- try this, or you'd miss first number     {         a[i + 1] = a[i];         i--;     }      a[i + 1] = key; } 

also, if want use professor's code, ignore 0-th element there.

on side note, did contact? rivest? corman? next time confused think i'll try contact him too, since seems professor reply mails:)