• C

How to sort a linked list ?

Hi, I've been trying to sort a linked list with no success so far. I used the predefined function qsort (quicksort) with a custom comparison function, but haven't had luck so far. If anyone could help me I would really appreciate. Thanks

PtrHead   = first link of the list
nbModels = number of models in the list

/* Declarations */
typedef struct model* PtrModel;
typedef struct model
{
      char nameModel[MAX_CAR_MODELE];
      int nbPolygons;
      PtrPolygon headPolygon;
      PtrModel next;
}Model;

/* Calling the function */
qsort(( void *) PtrHead, nbModels, sizeof(Model), compareModel(PtrHead, PtrHead->next));

/* Comparison function */
int compareModel( PtrModel Ptrhead, PtrModel PtrCur)
{
     PtrModel ptr1 = (PtrModel *)Ptrhead;
     PtrModel ptr2 = (PtrModel *)PtrCur;
     int t=strcmp(ptr1->nameModele, ptr2->nameModele);
       Ptrhead= Ptrhead->next;
     if(t) return t;
     return strcmp(ptr1->nameModele, ptr2->nameModele);
}


Thanks,

Frank
The_Kingpin08Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Kent OlsenData Warehouse Architect / DBACommented:
Hi Frank,

qsort() won't work for this.  You're going to have to sort the list by modifying the list pointers.  There have been several discussions on the board about the quickest and easiest way to do this.  The discussions have been quite lively, and the conclusions usually the same -- there's not a concensus on the best way to sort a linked list.  The most efficient method is largely data dependent.

Since you've got the list in memory, one of the quickest and easiest is to build a table of pointers to the data in the list.  This is in addition to the list structure.  You then sort the pointers according to the data and rebuild the list.

However, if this is a class assignment, sorting a table pointer is probably not what the instructor has in mind.


Kent
0
The_Kingpin08Author Commented:
It is a class assignment, but how would it possible besides the table pointers method ? Maybe the best way would be to make a validation before the creation and the insertion of an item, or a long unefficient validation before printing ?

Thanks,

Frank

0
Kent OlsenData Warehouse Architect / DBACommented:

The easiest, is to insert the items into the correct location in the list.  The AddItem() function winds up being only slightly more logic than adding to the head of the list.  In fact, the function will look almost exactly like adding a member to the tail position, except the the controlling if() statement will have a slightly different test.

But this won't always solve your problem.  You might want the list sorted on one key for certain operations and sorted on another key later.  In this case there is a legitimate need to sort the list.

You can solve the alternate sort problem with an alternate AddItem() function.

  for (Member = HeadOfList; Member; Member = Member->Next)
    NewList = AddItemSortedBySomething (NewList, Member);
  HeadOfList = NewList;

Kent
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Creating Active Directory Users from a Text File

If your organization has a need to mass-create AD user accounts, watch this video to see how its done without the need for scripting or other unnecessary complexities.

sunnycoderCommented:
Hi Kent,

I believe the instructor could be looking for something like bubble sort. The statement says "How to sort a linked list?". I am inclined to believe that linked list already exists and Frank needs to write a function to sort the linked list.

Am I right Frank or am I reading too much between the lines? If insertion sort will do, then I do not think a class assignment would have any more data than a single int in a node, so you can take Kent's advise and add insertion in sorted order functionality.

PS: Kent, did you receive the reply for the mail? ... just wondering - did it get filtered to trash again?

cheers
sunnycoder
0
Kent OlsenData Warehouse Architect / DBACommented:
Hi Sunny,

Haven't gotten anything from you in quite a while.  Your old e-mail address is in my white list.  Do I need to add another address?  :)

Kent
0
sunnycoderCommented:
Hi Kent,

errr ... then check your junk folder .. I replied the same day that I got your mail on EE account ... EE account is an alias to my personal account, so the from field in the reply will not contain EE address. I am posting a yahoo address in the profile, add it to the clean list.

cheers
sunnycoder
0
Kent OlsenData Warehouse Architect / DBACommented:
All better now.  The only name that I had in my white-list was your old hotmail account.

(Perhaps I shouldn't have said that SunnyCoder has a hotmail account?)

Oh well......  :)
0
sunnycoderCommented:
Hi Kent,

:-D ... the hotmail account is dead ... If you were able to find the mail in junk, add that address to whitelist and we can keep communicating with that id. Else, use the yahoo mail-id (not yim id - it has no corresponding mail account) in the profile

cheers
0
Kent OlsenData Warehouse Architect / DBACommented:

Ok.  Let's check the filter.  Send me something....

0
sunnycoderCommented:
sent
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

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.