Sorting elements with cursor-based

[Whilliam]

Hello, Im trying to insert some integers to make a sorted list. I am using cursor-based.
Here is the function:

void insert_sorted(virtualheap *vh, list *l, int x)
{
	 int temp, *p;

	 if(vh->avail != -1)
	 {

		  temp = mymalloc(&(*vh));
		  vh->h[temp].elem = x;
		  for(p = l; *p != -1 && vh->h[*p].elem <= vh->h[temp].elem ; *p = vh->h[*p].next);


		  if(*p == -1)
				*p = temp;
		  else
		  {
				vh->h[temp].next = *p;
				*p = temp;
		  }
	 }
	 else
		  printf("No heap available\n");
}

Example, I will input 5, 2 and 1, it will work perfectly but if I will input 5, 3 and 6 (it is not in descending order), only 6 will be in the list. It will only work perfectly if I will input numbers in descending order.
Variable p is supposed to traverse through the list and stop when it reaches the correct position. I need to make variable p a pointer because I need it to change the value of the one it is pointing to. Variable l is only supposed to hold the first array of the list. I will only change it if x is smaller than any of the elements in the list.
The problem is, when p is traversing, variable l will still get p's value. I dont know any way for p to get l's value without changing l.
And yeah, the list should be a pass-by address.
Can anyone help me..

[Murtan]

So 'list' is an index into the virtual heap, and each entry in the virtual heap is a structure that has an elem (the value at that node) and a next (the index in the virtual heap for the entry with the next higher elem).

When there are no entries in the list, the list * l passed to this function will point to -1 (indicating end of list).

So when you add 5, 2, 1 we should end up with:

l = 2
vh->h[0].elem = 5       vh->h[0].next = -1
vh->h[1].elem = 2       vh->h[1].next = 0
vh->h[2].elem = 1       vh->h[2].next = 1

When you add 5, 3, 6 you should get:

l=1
vh->h[0].elem = 5       vh->h[0].next = 2
vh->h[1].elem = 3       vh->h[1].next = 0
vh->h[2].elem = 6       vh->h[2].next = -1

But you appear to be getting:

l=2
vh->h[0].elem = 5       vh->h[0].next = ?
vh->h[1].elem = 3       vh->h[1].next = ?
vh->h[2].elem = 6       vh->h[2].next = -1

The next debugging step would normally be to add some code to dump the entire virtual heap just to confirm what you have is what you think you have. However, I think I see your problem. int * p starts out pointing to the passed in value list * l .

The for loop on line 10 is supposed to 'walk through' the list until it finds where the new value is supposed to go, then it is supposed to update the next value of the record that should precede it. (Or update the list value if the new value is lower than any previous value.)

The for loop uses the expression *p = vh->h[*p].next to advance to the next record.

The problem is that what you are advancing is NOT the pointer p, but the value that the pointer points to. (It still appears to work, but the values will end up in the wrong place when you actually insert.)

Change the advance expression to p = &(vh->h[*p].next) so that the actual pointer gets updated.

[Whilliam]

wow! thanks Murtan! that solved the problem.