# recursive ascending order insertion sort

• April 8th, 2009, 02:36 PM
javajax
recursive ascending order insertion sort
i am working on a program.
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                 }         } }```
• April 8th, 2009, 03:53 PM
Lindley
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.
• April 8th, 2009, 04:37 PM
javajax
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.
• April 8th, 2009, 04:45 PM
Lindley
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.