Someone tell me whats wrong please :(

[BGM]

Hello,

should be an easy one for u guys.

i have an assignment at uni to do insertion sort on an array recursively.. ok i thought, think about the function normally then make it recursive..

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

that works fine to sort any array of length n.. woo

so then i try to make it recursive.. a snippet from main to initialise the function:

for (i=1;i<n;i++)
	{
		temp = array[i];
		j = i-1;
		sort(array,temp,j);
	}

and the sort function replacing the while loop:

void sort(int* a, int temp, int j)
{
	if (( a[j] > temp) && (j >= 0 ))
	{
		a[j+1] = a[j];
		j--;
		sort(a,temp,j);
	}
	a[j+1] = temp;
}

to me, reading that through.. it should work, it tests to see if the number prior to 'temp' is larger, if so it gets moved along til the number infront of temp isnt larger and when the test fails, the funciton writes it to the empty slot

but iv been messing around with it now for an hour or so (skills), and i dunno whats the matter, i either get no output, too much output, wrong output in a seemingly random manner and its really pissing me off .. any help would be great, im sure its something glaringly obvious or what iv done is so completely wrong its laughable, either way, thanks very much for looking

cheers

 

[lomn75]

well, you should first be able to demonstrate to yourself that it works in pseudocode. Take the trivial case (either 0 or n, as appropriate) and verify it, then try 1/n-1, then the general case.

Once that's done and you're coding the implementation, the debugger is your friend. Watch the variables as you cycle through the recursion. This is for finding trivial errors (addition instead of subtraction).

The hard work should be done as above, before you write a line of relevant code. I find whiteboards ideal, with pen/paper being a good alternative.