How to sort doubly linked list with multiple elements in C?

Question

I need to sort a doubly linked list with multiple elements, the structure I have is the following:

typedef struct node {
   int code;
   char name[40];
   char job[40];
   int salary;
   struct nodo *next;
   struct nodo *prev;
} node;

In detail, I have to create a function that receives a *Head and sort the elements by their salary, (lower to higher) e.g

node1->salary = 1000;
node2->salary = 500;
node3->salary = 1500;

The function has to order so the order sets to node2, node1, node3. Here's what I tried so far:

void sort(node *head) 
{ 
    int swapped, i; 
    node *ptr1; 
    node *lptr = NULL; 

    if (top == NULL) 
        return; 

    do
    { 
        swapped = 0; 
        ptr1 = head; 

        while (head->next != lptr) 
        { 
            if (ptr1->salary > ptr1->next->salary) 
            {  
                // This part actually only changes the positions of the salary
                // I need to change the position of all the elements
                node *temp;
                temp->salary= ptr1->salary;
                ptr1->salary= ptr1->next->salary;
                ptr1->next->salary= temp->salary;
                swapped = 1; 
            } 
            ptr1 = ptr1->next; 
        } 
        lptr = ptr1; 
    } 
    while (swapped); 
} 

Answer 1

Here is an example, sorting in both asc and desc order

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

typedef struct node {
   int code;
   char name[40];
   char job[40];
   int salary;
   struct node *next;
   struct node *prev;
} node;

void swapNodes(node *a, node *b) {
  node tmp = *a;
  a->code = b->code;
  strcpy(a->name, b->name);
  strcpy(a->job, b->job);
  a->salary = b->salary;
  b->code = tmp.code;
  strcpy(b->name, tmp.name);
  strcpy(b->job, tmp.job);
  b->salary = tmp.salary;
}

//////////////////////////////////////////////////////////////////////////////////////
// \brief  Sort the linked list in ascending or descending order
// \param  head        The head node of the list
//
// \param  isReversed  Whether to sort in asc or desc, false for asc and true for desc
//////////////////////////////////////////////////////////////////////////////////////
void sort(node *head, bool isReversed) {
  // store the current and the previous nodes
  node *currentNode, *previousNode;
  // store if there still a difference in the list means that we have some nodes not sorted
  bool difference;
  loopAgain:
    // looping again and assuming no more difference
    difference = false;
    currentNode = previousNode = head;
    // loop over the list
    while(currentNode != NULL) {
      currentNode = currentNode->next;
      // check for salary if the current salary is less than the previous and in ascending mode
      // then swap the nodes and the opposite in descending mode
      if(currentNode != NULL && (isReversed ? previousNode->salary < currentNode->salary :
          previousNode->salary > currentNode->salary)) {
        swapNodes(previousNode, currentNode);
        difference = true;
      }
      previousNode = currentNode;
    }
  // go to loop again since there still maybe no sorted nodes yet
  if(difference) {
    goto loopAgain;
  }
}

int main() {
  node n1 = {0, "a", "-", 3500, NULL, NULL},
    n2 = {0, "b", "-", 500, NULL, &n1},
    n3 = {0, "c", "-", 1500, NULL, &n2};
  n1.next = &n2;
  n2.next = &n3;
  printf("Before sort:\n%s)%d\n%s)%d\n%s)%d\n", n1.name, n1.salary, n2.name, n2.salary, n3.name, n3.salary);
  sort(&n1, false);
  printf("After ascending sort:\n%s)%d\n%s)%d\n%s)%d\n", n1.name, n1.salary, n2.name, n2.salary, n3.name, n3.salary);
  sort(&n1, true);
  printf("After descending sort:\n%s)%d\n%s)%d\n%s)%d", n1.name, n1.salary, n2.name, n2.salary, n3.name, n3.salary);
  return 0;
}

Output

Before sort:
a)3500
b)500
c)1500
After ascending sort:
b)500
c)1500
a)3500
After descending sort:
a)3500
c)1500
b)500