i have been given a code to sort a linked list that contains links (we call them maillons in french, sorry i don't really know how it's called in english) of Opera type, this is the definition of its structure :

typedef struct opera_s {
    char * titre; /* title */
    date * date_creation; 
    char * ville_creation; /* city of creation */
    individu * compositeur; /* composer*/
} opera; 

typedef struct individu_s {
        char * nom;   /* family name */
        char * prenom; /* first name*/
        date * naissance; /* date of birth */
} individu;

typedef struct date_s {
    unsigned int jour; /* day */
    unsigned int mois;  /* month */
    unsigned int annee; /* year */
} date;

also the definition of a single link and a list

struct maillon_s{
    opera * valeur; /* value of opera type */
    struct maillon_s * suivant;  /* the next link */
};
typedef struct maillon_s maillon;

struct liste_s{
    struct maillon_s * debut; /* first link */
    int taille; /* list size */
};
typedef struct liste_s liste;

and then the code to sort the list is :

void sort_list_title (liste * l) {
    maillon *p, *q;
    liste * tmp=create_empty_list(); 
    add_link_head_list(tmp,create_link()); /* a function that adds a link as head */
    while(!test_empty_list(l)){
       p=extract_link_from_head_list(l); /* function that extracts a link from the head of the list, thus reducing it and the extracted link's next will point towards NULL */
       q=tmp->debut;
       while((q->suivant!=NULL) && (strcmp(q->suivant->valeur->titre,p->valeur->titre)<0))
          q=q->suivant;
       p->suivant=q->suivant;
       q->suivant=p;
       tmp->taille  ;
    }
    destroy_link(extract_link_from_head_list(tmp));
    l->debut=tmp->debut;
    l->taille=tmp->taille;
    free(tmp);
}

i can't understand the strategy used in order to sort this linked list, can someone pls explain it to me (i have to understand this specific code bc the teacher gave it to us)? i can't even get the algorithm, i'd appreciate a demonstration with examples, and if you have a simpler code i'd be glad to know about it, thank u in advance

CodePudding user response：

This is sample working code

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node* next;
};

void display(struct node* head)//function to print linked list
{
    struct node* ptr = head;
    while (ptr)
    {
         printf("%d  ",ptr->data);
        ptr = ptr->next;
    }
}

struct node* newNode(int data)
{
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertion_sort(struct node** head, struct node* newNode)//function to insert data in sorted position
{
    //If linked list is empty
    if (*head == NULL || (*head)->data >= newNode->data)
    {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    //Locate the node before insertion
    struct node* current = *head;
    while (current->next != NULL && current->next->data < newNode->data)
        current = current->next;

    newNode->next = current->next;
    current->next = newNode;
}

int main(void)//main method
{
    int n,k;
printf("Enter the size of linked list :\n");
    scanf("%d",&n);
    struct node* head = NULL;
    
    //constructing linked list
    for (int i = n-1; i >= 0; i--){
    
    printf("\nEnter data you want to insert: ");
    scanf("%d",&k);
    insertion_sort(&head, newNode(k));
    }
    printf("Sorted Linked list after insertion : ");
    display(head);

    return 0;
}

CodePudding user response：

Commented code. For english, maillon would be called a node . The code creates a temporary list tmp and a temporary head node in list tmp, then removes maillon's from list l one at a time and inserts them into order into list tmp, until list l is emptied. The temporary head node in list tmp is deleted. List l debut and taille are set to list tmp values. List tmp is freed.

void sort_list_title (liste * l) {
    maillon *p, *q;                           /* declare p and q as pointers to maillon */
    liste * tmp=create_empty_list();          /* create an empty list tmp */
    add_link_head_list(tmp,create_link());    /* add a temp head node to list tmp */
    while(!test_empty_list(l)){               /* while the orignal list is not empty */
       p=extract_link_from_head_list(l);      /*  p = removed debut maillon from list l */
       q=tmp->debut;                          /*  q = ptr to temp head node in list tmp */
           /* advance q until end of list or until q maillon is >= p maillion */
       while((q->suivant!=NULL) && (strcmp(q->suivant->valeur->titre,p->valeur->titre)<0))
          q=q->suivant;
           /* insert p between q and q->suivant */
       p->suivant=q->suivant;                 /*  set p's suviant to q's suivant */
       q->suivant=p;                          /*  set q's suviant to p */
       tmp->taille  ;                         /*  increment list l count */
    }
    destroy_link(extract_link_from_head_list(tmp)); /* remove | free head node from list tmp */
    l->debut=tmp->debut;                      /* set list l debut to the sorted tmp debut */
    l->taille=tmp->taille;                    /* set list l count to list tmp count */
    free(tmp);                                /* free list tmp */
}