Insert Sort from T Cormen Book

Question

I am working on Cormen's Introduction to Algorithms book, and I created the following from pseudocode. However, the first two elements of the array do not seem to be sorted. I can’t detect the error (possibly because I was late). So I was wondering if anyone could see at a 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; } 

Answer 1

I did not look too closely, but I think that the pseudo-code of the book uses unidirectional indexing, and for encoding in C (or most modern languages) you need to configure it to index with zero value.

The main suspect

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

If you want to start with 1 instead of 2.

Termination condition

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

You may also need to change it so that you are above -1, not 0.

EDIT:

After a little closer look, I'm sure you also need to tweak this while .

In addition, you should, of course, look at all the upper limits for similar questions separately.

Answer 2

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

Answer 3

Actually, your code is correct, but the problem is there in initializing the for loop. pseudo code to sort insert:

 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 

In fact, your code does not consider the first element of the array. It just looks at the sort from the second element of the array, getting this type of result.

Just change the initialization of j to 1 and it will work correctly.

Answer 4

You can use this code, I fixed 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"; } } 

Answer 5

Take a look at the CLRS insertion sorting algorithm translated into 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]+" "); } } 

Answer 6

 Book 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] << " "; }