[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

How to sort a linked list ?

Posted on 2004-11-17
10
Medium Priority
?
574 Views
Last Modified: 2010-04-15
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
0
Comment
Question by:The_Kingpin08
  • 5
  • 4
10 Comments
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12607764
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
 

Author Comment

by:The_Kingpin08
ID: 12607854
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
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 2000 total points
ID: 12608120

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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 45

Expert Comment

by:sunnycoder
ID: 12611295
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
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12613845
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 12622049
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
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12624678
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 12652472
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
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12654272

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

0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 12662243
sent
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

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…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
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.
Suggested Courses

872 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