Programming Forums - Linked Lists: Insertion Sort, RECURSIVELY

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - Linked Lists: Insertion Sort, RECURSIVELY (http://www.programmingforums.org/showthread.php?t=15200)

jason999x

Feb 17th, 2008 10:26 PM

Linked Lists: Insertion Sort, RECURSIVELY

how does one do a recursive insertion sort on a linked list, particularly with these given parameters:

InsertSortR(std::string ItemName, ListItemNode* &node);

Also, how does one do a recursive traverse of a linked list, AND something else at the same time, such as add up values in that linked list?

Sane	Feb 17th, 2008 11:19 PM

Re: Linked Lists: Insertion Sort, RECURSIVELY

I'll answer your second question. Maybe that will help you think up the answer to your first question.

function sumlist(linkedListNode node), returns an integer:

    if node is null:

        return 0

    else:

        Look at the current node here

        

        Once we're done looking, continue traversing and summing as we go

        return node.value + sumlist(node.next)

jason999x

Feb 19th, 2008 6:11 PM

Re: Linked Lists: Insertion Sort, RECURSIVELY

thanks but they do seem to be separate things... I don't think I ever clearly explained myself on the whole traverse thing... it's confusing because I can't figure out where the variable to be added onto is in this massive scheme of classes, i/o, and pointers. But InsertSortR should be more clear, I just need to know how to implement it!

Wizard1988

Feb 19th, 2008 9:21 PM

Re: Linked Lists: Insertion Sort, RECURSIVELY

Because you are traversing the list recursively it is acting somewhat like a stack.
Once you take a look at a node you return its value + the value of the next, this keeps on going until you hit the last node when you return the value of all the nodes added up.

Hopefully this clears it up.

Sane	Feb 19th, 2008 11:47 PM

Re: Linked Lists: Insertion Sort, RECURSIVELY

Quote:

Originally Posted by jason999x (Post 141237)

But InsertSortR should be more clear, I just need to know how to implement it!

InsertSort will be very similar to the psuedocode I posted. Simply compare the value of the current node against the one passed through the function. If it should be inserted before the current node, then create a new node, link it to the next, and return the new node. In the even that the current node is not modified, it should return itself. The calling function should reassign the next node to the return value of the recursion. All done. Want that in psuedocode, or will that ruin the fun?

All times are GMT -5. The time now is 4:19 AM.