sort a linked list of struct in c

Question

I am trying to sort a linked list in an ascending order according to the element of the struct"capacite" . But it doesn't give a result. What is the mistake i am making? Here is my code

typedef struct avion avion;

typedef avion*  aliste;

struct avion
{
    char code[20];
    int capacite;
    char etat;
    int date;
    int nvols;
    aliste svt;
};

i have created the list. and following the function that sort it:

void tri(aliste L)
{
   aliste i,j,min,tmp;
   for (i=L; i->svt != NULL; i=i->svt)
   {
      min=i;
      for (j=i->svt; j != NULL; j=j->svt)
      {
        if (j->capacite < min->capacite)
           min=j;
      }
       if (min != i)
      {
       tmp=min;
       min=i;
       i=tmp;
      }
    }
}

You are not changing `->svt` of any item at all so the order of the items in the list obviously cannot get changed. — Roman Hocke, Mar 12 '21 at 08:05
When you swap, you want to change the positions of two elements in the list. In a linked list, you must do that by adjusting the `svt` fields of the elements before and of the list head `L`. The calling function must also be made aware if the head changes. — M Oehm, Mar 12 '21 at 08:06
Easy way? Create an array of pointers and traverse your list assigning the pointers to your array -- then `qsort()` the array based on the needed struct member. That does not alter the ordering of your list, but provides an array of pointers in sorted order. Otherwise, you can sort your list swapping nodes in your list which will be computationally expensive. You will want to review: [Is it a good idea to **typedef** pointers?](http://stackoverflow.com/questions/750178/is-it-a-good-idea-to-typedef-pointers). — David C. Rankin, Mar 12 '21 at 08:20
The biggest mistake you're sort is making is it isn't actually sorting *anything*. It just runs through the existing list, finding the "minimum" of the remaining forward sequence, then swaps some local pointers around, but never changes the actual list ordering because the one thing that determines that order, the chain of `svt` pointers, is never touched. — WhozCraig, Mar 12 '21 at 08:23

score 1 · Answer 1 · answered Mar 12 '21 at 08:45

It looks like you are trying to bubble sort your list. A quick and dirty fix would be to swap the contents of your nodes:

void tri(aliste L)
{
   aliste i,j,min;
   avion tmp;
      ...
      if (min != i)
      {
       tmp=*min;
       *min=*i;
       *i=tmp;
      }
    }
}

The good news here is that the L pointer passed from the caller still points to the beginning of the list. The downside if that it copies the structures while changing only the svt pointers would be much more efficient. But:

you will have to return to the caller a pointer to the new head
moving elements from a singly linked list requires to record the previous element

As you use bubble sort which is not a very efficient algorithme, I assume that you only intend to process small lists and that performance is not essential, so you are on your own...

ralf htp · Answer 2 · 2021-03-12T08:55:09.133

0

A common way to implement a linked list of structs in C is in https://www.geeksforgeeks.org/linked-list-set-1-introduction/

Basically inside the struct there is a pointer next to the next node in the linked list, what establishes the linked list functionality :

struct Node { 
    int data; 
    struct Node* next; 
};

For this more common implementation of a linked list in C you find source code for many sorting algorithms (qsort, mergesort,...) on the net. You have to implement functionality for more than one parameter in such an example because your nodes (of the linked list) have multiple data fields...

Sorting linked list by multiple parameters

typedef avion* aliste; Is it a good idea to typedef pointers?

edited Mar 12 '21 at 08:55

answered Mar 12 '21 at 08:38

ralf htp

9,149
4
22
34

1

So.. what's specifically wrong with the OP's sorting algorithm and how can it be fixed? Pretty sure that was the question. If you feel [the linked question](https://stackoverflow.com/questions/33728844/sorting-linked-list-by-multiple-parameters) answers this, either suggest it as a duplicate, or point out specifically what the OP is doing wrong. As written this answer would be considered as a"link-only answer". I.e it doesn't actually address the question except to provide links to other things that might, without elaborating *how* they're relevant. – WhozCraig Mar 12 '21 at 08:45
What i want to say with this answer is ... the code should be rewritten in a more common way. This use of proven and accepted coding techniques is also the intention behind *design patterns*. It is uncommon practice to implement a linked list like this and if it doesn't provide advantages like speedup or something nobody has to reinvent the wheel and overcomplicate simple tasks – ralf htp Mar 12 '21 at 08:51

sort a linked list of struct in c

2 Answers2