CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    Apr 2009
    Location
    chicago
    Posts
    9

    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
    		}
    	}
    }

  2. #2
    Lindley is offline 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. #3
    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. #4
    Lindley is offline 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.

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
  •  





Click Here to Expand Forum to Full Width

Featured