insertion sort error

hi,

i have this code for insertion sort. the only problem i have with it is that the very first item in the array is not being sorted. i can't put my finger on it. could someone please tell me where i went wrong?

barneygumble742

Code:

#include <iostream>
using namespace std;

int *ins_sort(int *array, int size);

int main()
{
int i=0, size=0, x=0;

int A[] = {5, 12, 2, -3, 0, 1, 1, 2, 4, 12};

	size = sizeof(A)/sizeof(A[0]);
	cout << "this array has " << size << " items." << endl << endl;

	ins_sort(A, size);

	for(i=0; i<size; i++)
	{
		cout << A[i] << endl;
	}

return 0;
}

int *ins_sort(int *array, int size)
{
int i=0, j=0, key=0;
int *start = array;

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

return start;
}

The first time through your for loop, j = 0. Does your while loop then execute? Does array[0] ever get examined?

Code:

for(i=1; i<size; i++)

That should start at zero, although I realize that's not possible because of this line:

Code:

j = i-1;

I would use an if to handle the first case (i==0).

Code:

while (array[j]>key)

hi...that is the change i made and it works perfectly now.

in the for loop, it had the same problem even when @ i=1;

thanks,
barneygumble742