recursive ascending order insertion sort

i am working on a program.

working with linked lists.

i am using an insort recursively to do an ascending sort.

i have a method called retrieve that retrieves the value of a node.

how would i get started to code this

Code:

`void Link::insort1(int nodeNumber)`

{

if (nodeNumber > 1)

{

nodeNumber -= 1;

remove(headPointer->next, headPointer->data);

int i, j;

for(i = 0;i < nodeNumber;i ++)

{

... code help

}

}

}

Re: recursive ascending order insertion sort

Difficult to be sure without more information (and more code!), but if you're removing the first element of the list, then presumably the next step is to traverse the list until you find an element larger than it, and then place it before that element.

Re: recursive ascending order insertion sort

we want to

1. remove

2. loop

3. retrieve

4. insert

some instructions for:

If the number of nodes is greater than 1, then perform a recursive call passing a reduced size. For the base case, remove the element from the list that is supposed to be placed in its sorted position (lets call it elementN). Loop through the portion of the list that has already been sorted until the position for elementN is found. Now insert elementN into the correct position.

Re: recursive ascending order insertion sort

Are you required to use that function signature? When the underlying data structure is a linked list, passing an index is rarely the best approach to anything. I would think some pseudocode like...

Code:

`PROCEDURE insertsort(startnode)`

IF (startnode is the only node) DONE

ELSE

insertsort(startnode->next);

FOR all nodes after startnode, now sorted

IF startnode goes between this node at the next

INSERT startnode between them

DONE

END IF

END FOR

END IF

Remember to consider the special cases when startnode could go at the very beginning or very end of the list.