CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: recursive ascending order insertion sort

1. Junior Member
Join Date
Apr 2009
Location
chicago
Posts
9

## 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;
int i, j;
for(i = 0;i < nodeNumber;i ++)
{
... code help
}
}
}```

2. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

## 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.

3. Junior Member
Join Date
Apr 2009
Location
chicago
Posts
9

## 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.

4. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

## 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•