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); 
}

Instead of node *temp, use node temp. Then copy everything into the temp struct like this: temp.salary = ptr1->salary, strcpy(temp.name, ptr1->name), etc. — user3386109
– user3386109, Commented Jun 6, 2020 at 19:34
The simplest solution is to use a temporary array of pointers to your list elements, call qsort to sort the array, then rebuild the list using the sorted array. If you don't want to use any temporary storage, then you'll need to write your own merge sort or quicksort or something similar. — Tom Karzes
– Tom Karzes, Commented Jun 6, 2020 at 19:37
Implement merge sort algorithm on the list. This algorithm doesn't require random access to elements. en.wikipedia.org/wiki/Merge_sort — Maxim Egorushkin
– Maxim Egorushkin, Commented Jun 6, 2020 at 20:27

Vlad from Moscow · Accepted Answer · 2020-06-07 00:18:17Z

For starters there is a typo

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

There shall be

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

Secondly, if you want to sort a list then you should sort the order of its nodes not swap values of data members of nodes. For example in main there can be declared a pointer to some node. If you will sort the list by swapping values of data members of nodes then the pointer will be invalid because data members of the pointed node was changed.

Thirdly, You should place all data members except the pointers next and prev in a separate structure. In this case function declarations will look much simpler because instead of passing several initializers to functions you will need to pass only one object of the structure type.

For example

typedef struct Person
{
    int  code;
    char name[N];
    char job[N];
    int  salary;
} Person;

typedef struct Node 
{
    Person person;  
    struct Node *prev;
    struct Node *next;
} Node;

At last if you deal with a doubly-linked list then it is supposed that you can add new nodes to the beginning and to the end of the list. It means that you should keep two pointers: one will point to the first node of the list and other - to the last node of the list. A consequence of this is that you should declare one more structure that will describe the list like for example

typedef struct List
{
    Node *head;
    Node *tail;
} List;

Now when all is prepared it is time to show how the method bubble sort can be applied to such a list.

Here is a demonstrative program.

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

enum { N = 40 };

typedef struct Person
{
    int  code;
    char name[N];
    char job[N];
    int  salary;
} Person;

typedef struct Node 
{
    Person person;  
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct List
{
    Node *head;
    Node *tail;
} List;

int push_back( List *list, const Person *person )
{
    Node *new_node = malloc( sizeof( Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->person = *person;
        new_node->prev   = list->tail;
        new_node->next   = NULL;

        if ( list->tail == NULL )
        {
            list->head = list->tail = new_node; 
        }
        else
        {
            list->tail = list->tail->next = new_node;
        }
    }

    return success;
}

void display( const List *list )
{
    for ( Node *current = list->head; current != NULL; current = current->next )
    {
        printf( "code = %d, name = %s, job = %s, salary = %d\n",
                current->person.code, current->person.name, 
                current->person.job, current->person.salary );
    }
}

void swap( Node **current )  
{  
    Node *tmp = *current;  

    *current = ( *current )->next;  

    tmp->next = ( *current )->next;
    ( *current )->next = tmp;

    ( *current )->prev = tmp->prev;
    tmp->prev = *current;

    if ( tmp->next != NULL )
    {
        tmp->next->prev = tmp;
    }
}

void clear( List *list )
{
    while ( list->head != NULL )
    {
        Node *current = list->head;
        list->head = list->head->next;
        free( current );
    }

    list->tail = list->head;
}

void sort( List *list, int cmp( const void *, const void * ) )
{
    if ( list->head != NULL )
    {
        int first_iteration = 1;

        for ( Node **first = &list->head, *sorted = NULL, *last = NULL;
              ( *first )->next != last;
              last = sorted )
        {
            Node **current = first;
            sorted = ( *first )->next;

            for ( ; ( *current )->next != last; current = &( *current )->next )
            {
                if ( cmp( &( *current )->person, &( *current )->next->person ) > 0 )
                {
                    swap( current );
                    sorted = ( *current )->next;
                }
            }

            if ( first_iteration )
            {
                list->tail = *current;
                first_iteration = 0;
            }               
        }             
    }         
}

int cmp_by_salary( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return ( right->salary < left->salary ) - ( left->salary < right->salary );
}

int cmp_by_code( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return ( right->code < left->code ) - ( left->code < right->code );
}

int cmp_by_name( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return strcmp( left->name, right->name );
}

int main(void) 
{
    List list = { .head = NULL, .tail = NULL };

    Person person[] =
    {
        { .code = 1, .name = "RaCo", .job = "programmer", .salary = 1000 },
        { .code = 2, .name = "Another RaCo", .job = "programmer", .salary = 500 },
        { .code = 3, .name = "One more RaCo", .job = "programmer", .salary = 1500 },
    };
    const size_t n = sizeof( person ) / sizeof( *person );

    puts( "Original list:" );
    for ( size_t i = 0; i < n; i++ )
    {
        push_back( &list, person + i );
    }

    display( &list );
    putchar( '\n' );

    sort( &list, cmp_by_salary );

    puts( "list sorted by salary:" );
    display( &list );
    putchar( '\n' );

    sort( &list, cmp_by_name );

    puts( "list sorted by name:" );
    display( &list );
    putchar( '\n' );

    sort( &list, cmp_by_code );

    puts( "list sorted by code:" );
    display( &list );
    putchar( '\n' );

    printf( "Debug output. The pointer tail points to %s\n", list.tail->person.name );

    clear( &list );

    return 0;
}

The program output is

Original list:
code = 1, name = RaCo, job = programmer, salary = 1000
code = 2, name = Another RaCo, job = programmer, salary = 500
code = 3, name = One more RaCo, job = programmer, salary = 1500

list sorted by salary:
code = 2, name = Another RaCo, job = programmer, salary = 500
code = 1, name = RaCo, job = programmer, salary = 1000
code = 3, name = One more RaCo, job = programmer, salary = 1500

list sorted by name:
code = 2, name = Another RaCo, job = programmer, salary = 500
code = 3, name = One more RaCo, job = programmer, salary = 1500
code = 1, name = RaCo, job = programmer, salary = 1000

list sorted by code:
code = 1, name = RaCo, job = programmer, salary = 1000
code = 2, name = Another RaCo, job = programmer, salary = 500
code = 3, name = One more RaCo, job = programmer, salary = 1500

Debug output. The pointer tail points to One more RaCo

As you can see using the same one function sort you can sort the list by any data member of the structure Person. You need not to write a new sorting function each time when the sorting criteria must be changed.

If you need to sort the list for example by data member salary in the descending order then just exchange variables in the return statement of comparison function

int cmp_by_salary( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return ( right->salary < left->salary ) - ( left->salary < right->salary );
}

like

int cmp_by_salary_desc( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return ( left->salary < right->salary ) - ( right->salary < left->salary );
}

and call the function sort as

sort( &list, cmp_by_salary_desc );

Saadi Toumi Fouad · Accepted Answer · 2020-06-06 21:57:29Z

0

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

edited Jun 6, 2020 at 21:57

answered Jun 6, 2020 at 21:30

Saadi Toumi Fouad

2,8322 gold badges7 silver badges20 bronze badges

3 Comments

RaCo Over a year ago

Thank you so much!

WhozCraig Over a year ago

Worth noting, this solution doesn't swap nodes; it swaps content while leaving the node links in the original order. In short, it's exactly the opposite of what you want in dynamic node order changing. Ideally the only things modified in a proper solution are the pointer-to-node members next and prev. Therein lays the likely solution the initiator of this academic assignment likely intended.

Paebbels Mar 23 at 16:13

This solution is inefficient due to many strcpy calls.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related