Sort in alphabetical order a List in c

Question

Hi i am writing a program that manage a list of student, i am using a list, each element is described like this:

struct student
{
    char lastname[50];
    char name[50];
    char date_of_birth[50];
    char height[50];
    struct student *next;
};

struct student *root=0; //this is the root node

This is how i add element to the list:

void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50])
{
    if(*root == 0)
    {
        *root = malloc(sizeof(struct student));
         strcpy((*root)->lastname,lastname);
         strcpy( (*root)->name,name);
         strcpy( (*root)->date_of_birth,date_of_birth);
         strcpy( (*root)->height,height);

        (*root)->next = 0;
    }
    else
    {
        add_element(&(*root)->next,lastname,name,date_of_birth,height);
    }
} 

I also wrote 2 function, one is for reading from a file, the other is to write the file, the file contains all the students, everything works but i need a function to sort all the element in alphabetical order by lastname, i tried to write one, but it doesn't work, it keeps crashing.

I tried a lot of things and they didn't work, this is one attempt, and it doesn't work :-(

please help me

void sort(struct student *head)
{
    struct student **current;
    struct student *tmp;

    for(current = &head ; *current !=NULL ; current = (*current)->next)
    {
        if((*current)->next == NULL)
        {
            break;
        }
        switch(strcmp((*current)->lastname,(*current)->next->lastname))
        {
            case 0:
            {
                printf("user not valid");
                break;
            }

            case 1:
            {
                tmp = *current;
                *current = (*current)->next;
                (*current)->next = tmp;
                break;
            }
        }
    }
}

Answer 1

After including remarks from comments to correct the proposed source code, the algorithm to sort the linked-list is missing some steps. At least, to sort a linked-list, it is necessary to have two loops. The choice used of a struct student **current access will be complex for a two nested loops.

Here is another powerful sorting function using the optimized qsort() function.

Step 1 - before showing the function, to sort a list, the root pointer shall be modified.

First method, used for the add_element() by sending the address of the pointer.

void sort(struct student **root)
{
...
}

Second method, to return the modified root.

struct student *sort(struct student *root)
{
...
    return (root);
}

Step 2 - the function sort() using qsort() quicksort function.

The method allocates a temporary array of pointers in order to have a fixed-size element to be sorted.

1. The first loop is necessary to know the number of pointers to be sorted (if lower than 2, no sort is needed);
2. After allocating the array of struct student *, fill the array by using a loop to each item of the linked-list;
3. Call the qsort() function by using the customized comparison function node_compare() (see next step);
4. Restore the linked-list with the sorted pointers by forcing the value of the struct student *next (the first is *root and the last is pointing to NULL).
5. free the temporary array of struct student *;

That's all.

//
void sort(struct student **root)
{
    struct student *tmp;
    struct student **array;
    int i,icount;

    // number of nodes to be sorted
    for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++);
    if (icount<2) {
        // no sort needed
        return;
    }

    // allocate an array of pointers
    array = (struct student **)malloc(icount*sizeof(struct student *));
    // push linked-list into array of pointers
    for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++) {
        array[icount]=tmp;
    }

    // quicksort using node_compare() customized function
    qsort(array, icount, sizeof(struct student *), node_compare);

    // pop linked-list from array of pointers
    *root = array[0];
    (*root)->next = NULL;
    for(tmp = *root,i = 1;i<icount;i++) {
        tmp->next = array[i];
        array[i]->next = NULL;
        tmp = tmp->next;
    }
    // free the allocated array of pointer
    free(array);
}
//

Step 3 - the comparison function node_compare() needed to qsort().

The function shall return a signed comparison as strcmp() does.

int node_compare(const void * a, const void * b)
{
    // restore node pointers
    struct student *node_a = *((struct student **)a);
    struct student *node_b = *((struct student **)b);

    if (node_b==NULL) return (-1); // force 'node_a'
    if (node_a==NULL) return (+1); // force 'node_b'
    // use the strcmp() function
    return (strcmp(node_a->lastname,node_b->lastname));
}

Enhancement - because the add_element() is using a recursive call not compliant with a long linked-list, here is a quite simple non-recursive algorithm.

If the recursive algorithm limits the size to few-centuries of elements, the proposed one has been tested with 100,000 elements (40Mb linked-list), generated randomly and sorted.

void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50])
{
    struct student **current;

    for(current = root; *current !=NULL ; current = &((*current)->next));
    *current = (struct student *)malloc(sizeof(struct student));
    strcpy((*current)->lastname,lastname);
    strcpy( (*current)->name,name);
    strcpy( (*current)->date_of_birth,date_of_birth);
    strcpy( (*current)->height,height);

    (*current)->next = NULL;
}