-
April 8th, 2009, 02:36 PM
#1
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
}
}
}
-
April 8th, 2009, 03:53 PM
#2
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
#3
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
#4
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.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|