Solved

'InsertionSort'ing a linked list

Posted on 1998-10-23
7
210 Views
Last Modified: 2011-09-20
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
Comment
Question by:stuckart
7 Comments
 
LVL 2

Expert Comment

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

Author Comment

by:stuckart
Comment Utility
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
 
LVL 84

Expert Comment

by:ozo
Comment Utility
what have you tried?
0
Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

 

Author Comment

by:stuckart
Comment Utility
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
 
LVL 12

Accepted Solution

by:
rwilson032697 earned 100 total points
Comment Utility
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
 
LVL 12

Expert Comment

by:rwilson032697
Comment Utility
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 Comment

by:stuckart
Comment Utility
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

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now