Insertion Sort from T Cormen Book

Question

I am working through the "Introduction to Algorithms" book by Cormen, and I have created the following from pseudocode. However, the first two elements of the Array do not seem to be sorted. I cannot spot the error (possibly because its late). So I was wondering if anybody could see from first glance.

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(){
  int input;
  cout << "Enter length of desired array." << "\n";
  cin >> input;
  cout << "\n";

  int A [input];

  //Populate and print the Array.
  for(int i=0; i<input; i++){
    A[i] = rand()%99-1;
    cout << A[i] << " ";
  }

  cout << "\n";

  //Insertion sort.
  for(int j=2; j<input; j++){ //Iterate through the Array.
    int key = A[j]; //Store the current element into key.
    int i = j-1; //Iterator for while loop.
    while(i>0 && A[i]>key){ //Loop to insert A[j] into the sorted sequence.
      A[i+1] = A[i]; //Move the element.
      i=i-1; //New value of i.
      A[i+1] = key; //Update the key
    }
  }

  for(int i=0; i<input; i++){
    cout << A[i] << " ";
  }
  return 0;
}

Vendue

Have you tried debugging this? Are you running on a minimal dataset? – Slave

That book uses 1 based indexing iirc, which would be your problem. – Sethrida

Answer 1

I haven't looked too carefully, but I think the book's pseudocode uses one-based indexing, and for coding in C (or most modern languages) you need to adjust it to zero-based indexing.

The principal suspect is

for(int j=2; j<input; j++)

Where you might want to start at 1 instead of 2.

The termination condition

while(i>0 && A[i]>key)

might also need to be changed to ensure you're above -1 rather than 0.

EDIT:

After a bit closer look, I'm pretty sure you do also have to adjust that while.

You should also of course review all upper limits for similar off-by-one issues.

Sager

Answer 2

change to for (int j = 1; ...)

Soutane

Answer 3

Actually your code is correct but the problem in there in your for loop initialization. the pseudocode for insertion sort 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

Actually your code is not considering the first element of the array. It is just staring sorting from second element of the array that's you getting that type of result.

Just change the initialization of j to 1 and it would run correctly.

Auricula

Answer 4

You can use this code , I have corrected your error

#include<iostream>
#include<stdlib.h>
#include<cstdlib>

using namespace std;

int main(){
    int input;

    cout<< "Enter length of desired array";
    cin>>input;

    cout<<"\n";

    int A[input];

    for(int i = 0 ;i <input ; i++)
    {
        A[i] = rand() % 100;   
        cout<<A[i] << "\t";
    }

    cout<<"\n";

    for(int j =1; j<input ; j++)
    {   int i;
        int key = A[j];
        i = j-1;
        while( i >=0 && A[i] > key)
        {
            A[i+1] = A[i];
            i = i-1;
            A[i+1] = key;
        }
    }

    for(int i = 0 ;i <input ; i++)
    {
        cout<<A[i] << "\t";
    }
}

Benge

Answer 5

Take a look at the CLRS insertion sort algorithm translated in java.

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;

        System.out.println("i in for loop "+i);

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

Horsy

Should not the first for loop start from 1 (i.e. j=1). In insertion sort, first element is always sorted. Hence we start from the second element. In Java ,arrays indexes are 0-based. So, it must start from j=1 – Salver

Answer 6

Book's pseudocode uses one-based indexing, and for coding in C (or most modern languages) you need to adjust it to zero-based indexing.  
Make the following changes and it will work:

    for(int i=1; i<input+1; i++){
        A[i] = rand()%99-1;
        cout << A[i] << " ";
      }


  for(int j=2; j<input+1; j++){ //Iterate through the Array.
    int key = A[j]; //Store the current element into key.
    int i = j-1; //Iterator for while loop.
    while(i>0 && A[i]>key){ //Loop to insert A[j] into the sorted sequence.
      A[i+1] = A[i]; //Move the element.
      i=i-1; //New value of i.
      A[i+1] = key; //Update the key
    }
  }

    for(int i=1; i<input+1; i++){
        cout << A[i] << " ";
      }

Keep

Answer 7

here's the answer, read the explanation by Don Roby first.

start j = 1 and while loop should have i >= 0

Winifredwinikka