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

Question

I am working my way through the book Introduction to Algorithms, 3rd edition. One of the first things explained is the insertion sort. On page 18 there is some pseudo code:

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

INSERTION-SORT(A)
1 for j = 2 to A.length
2   key = A[j]
4   i = j - 1

5   while (i > 0 and A[i] > key)
6     A[i + 1] = A[i]
7     i = i - 1

8   A[i + 1] = key

It says that pseudo code is used so that it is easily translated to any kind of language (C, C++, Java, they don't mention, but I guess C# too). Since I program in C#, I translated it in LinqPad.

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

for (var j = 1; j < a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

a.Dump();

You're probably going to ask, why does j start at 1, when it clearly says 2? In the book, the array has an index starting at 1. And yes, I now I probably should have updated all the [i - 1] and [i + i] as well.

Anyways, after I was done, I run the code and notice that it doesn't actually sort correctly. The output is { 5, 1, 2, 3, 4, 6 }. It was late and should have stopped, but I struggled on to make the code correct. I did everything, even taking the pseudo code as is from the book (starting at 2). Still not the correct output.

I contacted one of the professors of the book, and he send me the code for the insertion sort, in C:

void insertion_sort(int *A, int n) {
  for (int j = 2; j <= n; j++) {
    int key = A[j];
    int i = j-1;

    while (i > 0 && A[i] > key) {
      A[i+1] = A[i];
      i--;
    }

    A[i+1] = key;
  }
}

Translated in C#:

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

for (var j = 2; j <= a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

I get an array out of bounds. Okay then maybe:

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

for (var j = 2; j <= a.Length - 1; j++)
{
    var key = a[j];

    var i = 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, this can't be correct. The pseudo code says 2 to array.Length. Is that 2 < array.Length, or 2 <= array.Length? What is going on here?

I personally think it is because of the 0 > 0 predicate in the while loop. It actually falls short one time each time.

My explanation (from my email sent to the professor, to lazy to type it all over):

The reason why the loop still ends up with { 5, 1, 2, 3, 4, 6 } is because of the i > 0 predicate. Every time in the while loop you subtract 1 of i (i--). This will eventually lead to 0 > 0 which ends up false (only 0 == 0 will return true), but this is when the loop still needs to run one more time. It continuously falls one short. It should go do the while loop 1 more time to properly sort.

Another explanation:

When j starts with 2, key == 4, i == 1 and a[i] == 2. The while loop won't run in this case because 2 > 0 but 2 isn't greater than 4.

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

While loop won't run because 4 is not greater than 6

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

While loop runs this time:

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

Again while loop because 2 > 0 and 4 > 1

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

Again while loop because 1 > 0 and 2 > 1

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

And here is where it goes (in my opinion) wrong. i is now equal to zero, but the while loop should run one more time to get the 5 out of the zero-th position.

The professor assures me that he is correct, but I can't get the right output. Where is my thinking going wrong?

---

The array in the C code that got sent to me by the professor was actually starting with an index of 1. I did not know this and checking upon C arrays I saw that they all start with 0. Yes, then the C code doesn't produce the correct output. The professor explained this to me and the pieces now fall into its place.

Renae

Every programming language I know indexes array from 0. I think MATLAB and R might be exceptions, but they're not real programming languages. :-) – Aceldama

Answer 1

I think the prof is using 1-based array notation, so with while (i > 0 && a[i] > key), you are missing the a[0] element in the loop. Change your initial code to this then it works:

for (var j = 1; j < a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i >= 0 && a[i] > key)  <----------- Try this, or you'd miss the first number
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

Also, if you want to use the professor's code, just ignore the 0-th element there.

On a side note, who did you contact? Rivest? Corman? Next time I get confused I think I'll try to contact him too, since it seems this professor reply mails:)

Thirtyone

Yes, i >= 0 indeed works. I did find out how to get the sorting to work albeit a bit different than your solution - it is one which you see a lot in other textbooks. Instead of having i >= 0 you would make the second predicate of the while loop a[i - 1] and have the first line in the while loop instead of a[i + 1] = a[i] like a[i] = a[i - 1]. The professor I contacted was Corman. Although he was nice enough to reply, he seemed quite offended that I thought that there was maybe a bug in the code. – Renae

"I think the prof is using 1-based array notation" - I got an email and this was indeed what was going on. I don't know why I got code with an array that is starting with an index of 1. I looked up C arrays and thought they always started with 0. – Renae

@Garth: Well I guess Corman is just being lazy:) And after all, since he use pointers, he could treat the input as if it is 1-based, because in his code the A[0] is never used. – Thirtyone

Answer 2

You should not think about translating the pseudocode, but about translating your understanding of the algorithm.

The array is completely unsorted at first. The algorithm works by taking successive unsorted elements and inserting them into the already sorted part. The starting "sorted part" is the first element, which is trivially "sorted". So, the first element to insert is the second. Which is the index of the second element? Your j has to start from there.

Then, i has to go through each of the sorted elements' indices, backwards, until it either finds the place to insert the current value or runs out of elements. So, where does it have to start, and where does it have to end? Take care that it actually looks at each element is has to.

Off-by-one errors are notoriously difficult to spot (and mixing notions of 1-based and 0-based arrays surely does not help), but don't just fiddle around until it seems to work. Try to understand what the code is actually doing.

Powerless

I totally agree - and that is what I did. I took it apart, looked at the moving parts and I get it. I get how it works, I can make it work. Backtracking it though to the pseudo code and the code I got from the professor I get confused because I simply can't get the right output. The professor is adamant about the fact that it works. – Renae

...And it works. The professor mailed me explaining me that the C array was starting with an index of 1. Since I thought that C arrays started with 0, the code didn't make sense. Now it does! – Renae

Answer 3

I believe your argument about i>0 is correct, regardless of what the prof. says. In the pseudo-code, the loop is while i > 0 and the array indexing starts with 1. In C#, array indexing starts with 0, therefore you should have while i >= 0.

Cornelia

Right. And I checked as well arrays in C, they also start with an index of 0. – Renae

Answer 4

I experienced the same problem. Below is the code in C which implements the above pseudo-code correctly. I am not using pointers, like other solutions.

Indeed, the tricky part about this was that the pseudo code is using 1-based array notations unlike most programming languages!

#include <stdio.h>

int main(void)
{
  int A[] = { 50, 20, 10, 40, 60, 30 };
  int j, key, len, i;
  len = (sizeof(A)) / (sizeof(A[0]));

    for (j = 1; j < 6; j++) {  <-- Change here
      key = A[j];
      // Insert key into the sorted sequence A[1 .. j - 1].
      i = j - 1;
      while (i >= 0 && A[i] > key) {  <-- Change here
          A[i + 1] = A[i];
          i--;
      }
      A[i + 1] = key;
    }

    for (int z = 0; z < len; z++) {
       printf("%d ", A[z]);
    }
   printf("\n");
 }

Simmie

Answer 5

I also came across your problem, and I found the solution to this. I coded the algorithm in java as below.

int a[] = {5,2,4,3,1};
    int key;
    int i;
    for(int j = 0; j < 5; j++)
    {
        key = a[j];
        i = j - 1;

        while(i>=0 && a[i]>key)
        {
            a[i+1]= a[i];
            i--;
        }
        a[i+1] = key;

        for(int k=0; k<a.length;k++)
        {
            System.out.print(a[k]+" ");
        }
    }

Nisa

Wow, thanks for coming back to it (after such a long time after being asked!) – Renae

Answer 6

Remember: A.length goes from 0 to n, so Length should be A.Length -1. I made this algorithm for my students in C++ in spanish, using that book. Is simple to translate in C#.

some translation so you can understand better

largo = length
actual = current
cadena = chain

void InsertionSort::Sort(char cadena[])
{
    int largo = strlen(cadena) - 1;
    char actual = '0';
    int i = 0;

    for (int j = 1; j <= largo; j++)
    {
        actual = cadena[j];
        i = j - 1;
        while(i >= 0 && cadena[i] > actual)
        {
            cadena[i + 1] = cadena[i];
            i--;
        }
        cadena[i + 1] = actual;
    }
}

Zoes

Answer 7

When translating to 0 array, be aware that you can miss the first element of the array. one way to solve it is to while i > -1;

Javascript:

A = [5,2,4,6,1,3];
for (let j=1; j < A.length; j++) {
  let key = A[j];
  let i = j-1;
  while(i>-1 && A[i] > key) {
    A[i+1] = A[i];
    i = i-1;
  }
  A[i+1] = key;
}
console.log(A);

Michellmichella