• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 260
  • Last Modified:

'InsertionSort'ing a linked list

Does anyone have code for Sorting a linked list using InsertionSort? Sorting by file size, date/time and then if necessary ID.  Without allocating any additional memory.  URGENT.  Bonus: if you determine the theoretical runtime.
0
stuckart
Asked:
stuckart
1 Solution
 
kellyjjCommented:
sounds like homework to  me. You should try this yourself and then  ask on the parts you are having probs with.
0
 
stuckartAuthor Commented:
This is not a homework question.  I am trying to teach myself.  It is easiest for me to learn by example.  The part that is hardest for me is the swapping of the pointers.
0
 
ozoCommented:
what have you tried?
0
What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

 
stuckartAuthor Commented:
Have in mind that I don't quite understand pointers that well.

void InsertionSort (Node *pHead)
  {
    Node *pCur = *pHead, *pTemp = *pHead;
    while( pCur)      <------   don't know what to put here, want to check if pCur is valid
      {
         pCur  =  pCur->pNext;
         while( pTemp->value > pCur->value)
            {
              swap them here.  Not sure how to move the pointers to do this.
            }
      }
}

In my Data structure I have   File, Date, ID  they are incremented by 1.
I'll put the exact code here, once my e-mail provider gets back online.  Figures huh.

thanks,
Jerry

0
 
rwilson032697Commented:
Your code is pretty much there. The while (pCur) is fine as long as pCur is set to NULL when it runs into the end of the list.

Instead of the inner while do this for the insertion:

        if( pTemp->value > pCur->value)
        {
           pTemp->nNext = pCur->pNext;
           pCur->pNext = pTemp;
        }

In terms of theoretical runtime this will be O(n squared). If you had used an array it would have been O(n log n).

To swap two pointers do this:

Node *SwapTemp = SecondNode;
SecondNode = FirstNode;
FirstNode = SwapTemp;

Cheers,

Raymond.
0
 
rwilson032697Commented:
Just a wee note: The O(n log n) for an array assumes you use a binary search to locate the insertion positon - the overhead of the actual array insertion operation is ignored.
0
 
stuckartAuthor Commented:
Thank you very much.  I actually had it almost exactly like you said, but I didn't have the *'s in the right place.  Thank you again,

Jerry Stuckart
stuckart@csd.uwm.edu

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now