Sorted Linked List on C Language

I have a problem here, I want to sort my Linked List with 3 data input, but when I executed this, only 1 data that be sorted. I have tried to mapping the temporary that will be replaced to a new nodes, but mapping only work on num_id data. Where is

For example:

  1. Data need to be sorted
21507 - John - Mathematics
21477 - Andrew - Biology
21905 - James - Physics
21322 - Sophia - Chemistry
  1. Expected result
21322 - Sophia - Chemistry
21477 - Andrew - Biology
21507 - John - Mathematics
21905 - James - Physics
  1. What I got
21322 - John - Mathematics
21477 - Andrew - Biology
21507 - James - Physics
21905 - Sophia - Chemistry

This is my script:

Nodes

struct nodes{
    int num_id;
    char name[30], lesson[30];
    struct nodes *link;
}*head, *current, *temp, *tail;

Sorted Linked List

void linked_list_sorted() {
    struct nodes *node, *temp_sorted;
    int temp_sortedvar_num_id, count_data=0;
    char temp_sortedvar_name[30], temp_sortedvar_lesson[50];
    node = head;
    while(node != NULL)
    {
        temp_sorted=node; 
        while (temp_sorted->link !=NULL)
        {
            if(temp_sorted->num_id > temp_sorted->link->num_id)
                {
                temp_sortedvar_num_id = temp_sorted->num_id;
                temp_sorted->num_id = temp_sorted->link->num_id;
                temp_sorted->link->num_id = temp_sortedvar_num_id;
                }
            else if(temp_sorted->name > temp_sorted->link->name)
                {
                strcpy(temp_sortedvar_name, temp_sorted->name);
                strcpy(temp_sorted->name, temp_sorted->link->name);
                strcpy(temp_sorted->link->name, temp_sortedvar_name);
                }
            else if(temp_sorted->lesson > temp_sorted->link->lesson)
                {
                strcpy(temp_sortedvar_lesson, temp_sorted->lesson);
                strcpy(temp_sorted->lesson, temp_sorted->link->lesson);
                strcpy(temp_sorted->link->lesson, temp_sortedvar_lesson);
                }
            temp_sorted = temp_sorted->link;
        }
        node = node->link;
    }
    temp_sorted = head;
    while(temp_sorted != NULL) {
        count_data++;
        printf("%d. %d - %s - %s\n", count_data, temp_sorted->num_id, temp_sorted->name, temp_sorted->lesson);
        temp_sorted = temp_sorted->link;
    }
}

and the last, this is my script to push the data to Linked List:

void push_data (int nim, char name[], char lesson[]) {
    // Push Step (Head, Mid, Tail)
    current = (struct nodes*)malloc(sizeof(struct nodes));
    current->nim = nim;
    strcpy(current->name, name);
    strcpy(current->lesson, lesson);

    if (head == NULL){
        head = tail = current;
    } else if (current->nim < head->nim) {
        current->link = head;
        head = current;
    } else{
        tail->link = current;
        tail = current;
    }
}

4 answers

  • answered 2021-09-11 18:21 Jeffrey Rennie

    Use merge sort for linked lists. Check out https://www.geeksforgeeks.org/merge-sort-for-linked-list/

  • answered 2021-09-11 18:27 Mani.

    When a comparision is success, you are only updating the value where the comparision is successful. For example in the following snippet

    temp_sortedvar_num_id = temp_sorted->num_id;
    temp_sorted->num_id = temp_sorted->link->num_id;
    temp_sorted->link->num_id = temp_sortedvar_num_id;
    

    you are only swapping the number as the number comparision failed, instead you need to swap all the values that are inside the node.

    Suggestion: instead of swapping all the values inside nodes write a method to swap the node references directly.

  • answered 2021-09-11 21:37 Neil

    For large enough inputs, it's hard to get faster than the standard library's qsort. (In many C libraries, it's inspired by Bentley, McIlroy, 1993, Engineering a Sort Function.) So much so, after a certain problem size, it's probably faster to allocate a whole new array with the contents of your linked-list, copy the entire linked-list into this array, qsort, and correct the pointers.

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <time.h>
    #include <assert.h>
    
    struct nodes{
        int num_id;
        char name[30], lesson[30];
        struct nodes *link;
    };
    
    static void fill(struct nodes *n) {
        size_t i, j;
        assert(n);
        n->num_id = rand();
        i = rand() / (RAND_MAX / ((sizeof n->name - 1) / 2) + 1)
            + ((sizeof n->name - 1) / 2);
        for(j = 0; j < i; j++)
            n->name[j] = rand() / (RAND_MAX / ('z' - 'a' + 1) + 1) + 'a';
        n->name[j] = '\0';
        i = rand() / (RAND_MAX / ((sizeof n->lesson - 1) / 2) + 1)
            + ((sizeof n->lesson - 1) / 2);
        for(j = 0; j < i; j++)
            n->lesson[j] = rand() / (RAND_MAX / ('z' - 'a' + 1) + 1) + 'a';
        n->lesson[j] = '\0';
    }
    
    static int compare(const struct nodes *a, const struct nodes *b) {
        return (a->num_id > b->num_id) - (a->num_id < b->num_id);
    }
    
    static int compar(const void *a, const void *b) { return compare(a, b); }
    
    int main(void) {
        size_t n;
        struct nodes ns[100000], *node, *head;
        const size_t ns_size = sizeof ns / sizeof *ns;
        srand((unsigned)clock());
        for(n = 0; n < ns_size; n++) fill(ns + n);
        qsort(ns, ns_size, sizeof *ns, &compar);
        for(n = 0; n < ns_size - 1; n++) ns[n].link = ns + n + 1;
        ns[n].link = 0;
        head = ns;
        for(node = head; node; node = node->link)
            printf("No. %d; name: %s; lesson: %s.\n", node->num_id,
            node->name, node->lesson);
        return EXIT_SUCCESS;
    }
    

    For small problem sizes, it's probably slower, as it changes the nature of your data structure and has a non-trivial set-up time. However, it's also very idiomatic. You could also allocate an array of pointers, qsort it, and use the pointers as markers while re-indexing.

  • answered 2021-09-11 21:40 trincot

    One of the problems in your sorted function is that it swaps the different members of nodes independently from each other. The condition you have for swapping the num_id member with the next is different from the condition for doing the same with name. Yet these should always stay together! So either you should not swap anything, or you should swap all members.

    As your code is responsible for pushing new data into the list, why not make sure the new node is placed at its sorted position in the list? Then you don't need sorted. In fact, your push_data already has the logic to put a node in front of the list when its num_id happens to be less than that of the current head node. If you do the same for other nodes, you'll always have your list sorted:

    void push_data (int num_id, char name[], char lesson[]) {
        // Use a local variable for referencing the new node:
        struct nodes *nodeNode = (struct nodes*)malloc(sizeof(struct nodes));
        nodeNode->num_id = num_id;
        strcpy(nodeNode->name, name);
        strcpy(nodeNode->lesson, lesson);
    
        if (head == NULL){
            head = tail = nodeNode;
        } else if (num_id <= head->num_id) {
            nodeNode->link = head;
            head = newNode;
        } else if (num_id >= tail->num_id) { // Add this condition
            tail->link = newNode;
            tail = newNode;
        } else { // Add this case:
            // Look for the insertion point, assuming list is sorted.
            // Use a local variable for current; not a member
            struct nodes *current = head;
            while (num_id > current->link->num_id) {
                current = current->link;
            }
            newNode->link = current->link;
            current->link = newNode;
        }
    }
    

    Now your list will always be sorted.

How many English words
do you know?
Test your English vocabulary size, and measure
how many words do you know
Online Test
Powered by Examplum