c - Sorting an array of linked list nodes

Question

I am writing a task scheduler in C. I managed to copy the nodes of linked list that contains the tasks to an array. I am. trying to implement the shortest job first scheduling algorithm and here is the code:

void schedule (struct Node* head){
    struct  Node* temp = head;
    struct Node** ordered_list = malloc(sizeof(struct Node*) * count);
        
    for (int i =0 ; i <count-1; i++) {
        ordered_list[i] = malloc(sizeof(struct Node));
        ordered_list[i] = temp;
        temp = temp-> next;
    }
    
    
    ordered_list[count-1] = temp;

    

    qsort(ordered_list, count, sizeof(struct Node ), cmpfunc);

the compare function is

    int cmpfunc(const void *a, const void* b){
        struct Node *node1 = (struct Node*) a;
        struct Node *node2 = (struct Node*) b;
        return (node1->task->burst - node2->task->burst);
    
    }

I am stuck with segmentation faults. I found that it is in the qsort function. Yet, I don't know what is wrong with it.

question from:https://stackoverflow.com/questions/65845798/sorting-an-array-of-linked-list-nodes

Answer 1

The method you're using to sort your linked list is to utilize an intermediate pointer-bed. i.e. a sequence holding all the node pointers, then using a canned sorting operation like qsort, then rebuilding the list.

The most fundamental problem is your comparator. It's wrong. The qsort comparator should expect the address of each element being sorted as arguments. Since you're sorting a sequence of pointers, the address of an element is therefore the address of a pointer. E.g. a pointer to pointer.

int cmpfunc(const void *a, const void* b)
{
    const struct Node * const * pp1 = a;
    const struct Node * const * pp2 = b;

    return ((*pp1)->task->burst - (*pp2)->task->burst);
}

In addition to that, but not related to your sorting issue, your build loop for your pointer bed leaks memory. This line:

ordered_list[i] = malloc(sizeof(struct Node));

is pointless. get rid of it.

---

Working Example

The following is a trivial working example you can adapt as needed.

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

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

int cmpfunc(const void *arg1, const void *arg2)
{
    const struct Node * const * lhs = arg1;
    const struct Node * const * rhs = arg2;
    return (*lhs)->data < (*rhs)->data ? -1 : (*rhs)->data < (*lhs)->data;
}

struct Node *schedule(struct Node *head)
{
    struct Node **arr = NULL;
    size_t capacity = 0;
    size_t size = 0;

    while (head)
    {
        if (size == capacity)
        {
            size_t new_capacity = capacity ? 2 * capacity : 1;
            void *tmp = realloc(arr, new_capacity * sizeof *arr);
            if (!tmp)
            {
                perror("Failed to expand sorting array");
                exit(EXIT_FAILURE);
            }

            arr = tmp;
            capacity = new_capacity;
        }

        arr[size++] = head;
        head = head->next;
    }

    if (size > 0)
    {
        qsort(arr, size, sizeof *arr,  cmpfunc);
        struct Node **pp = &head;
        for (size_t  i=0; i<size; ++i)
        {
            *pp = arr[i];
            pp = &(*pp)->next;
        }
        *pp =  NULL;

        // don't need this anymore
        free(arr);
    }

    return head;
}

int main()
{
    srand((unsigned)time(NULL));

    // build a random linked list
    struct Node *head = NULL, **pp = &head;
    for (int i=0; i<20; ++i)
    {
        *pp = malloc( sizeof **pp );
        (*pp)->data = 1 + rand() % 99;
        printf("%d ", (*pp)->data);
        pp = &(*pp)->next;
    }
    *pp = NULL;
    fputc('
', stdout);

    head = schedule(head);
    for (const struct Node *p = head; p;p = p->next)
    {
        printf("%d ", p->data);
    }
    fputc('
', stdout);

    // free the list
    while (head)
    {
        void *p = head;
        head = head->next;
        free(p);
    }
    
    return EXIT_SUCCESS;
}

Output (varies)

54 85 69 83 13 69 74 64 90 19 83 80 92 25 95 93 49 38 6 83 
6 13 19 25 38 49 54 64 69 69 74 80 83 83 83 85 90 92 93 95