asked on

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

Kent Olsen

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

The_Kingpin08

ASKER

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

ASKER CERTIFIED SOLUTION

Kent Olsen

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

sunnycoder

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

Kent Olsen

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

sunnycoder

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

Kent Olsen

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...... :)

sunnycoder

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

Kent Olsen

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

sunnycoder

sent