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

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
1 Solution

Commented:
sounds like homework to  me. You should try this yourself and then  ask on the parts you are having probs with.
0

Author 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

Commented:
what have you tried?
0

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

{
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

Commented:
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

Commented:
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

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