'InsertionSort'ing a linked list

Posted on 1998-10-23
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.
Question by:stuckart

Expert Comment

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

Author Comment

ID: 1253773
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.
LVL 84

Expert Comment

ID: 1253774
what have you tried?
Optimizing Cloud Backup for Low Bandwidth

With cloud storage prices going down a growing number of SMBs start to use it for backup storage. Unfortunately, business data volume rarely fits the average Internet speed. This article provides an overview of main Internet speed challenges and reveals backup best practices.


Author Comment

ID: 1253775
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.


LVL 12

Accepted Solution

rwilson032697 earned 100 total points
ID: 1253776
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;


LVL 12

Expert Comment

ID: 1253777
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.

Author Comment

ID: 1253778
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


Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
How to align numbers in C using the %d 2 104
Want to delete all my personal data 13 146
Detect CR LF to each line 12 169
Unable to start eclipse ? 17 153
Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

808 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