Sorted Linked List on C Language-CodePudding

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:

Data need to be sorted

21507 - John - Mathematics
21477 - Andrew - Biology
21905 - James - Physics
21322 - Sophia - Chemistry

Expected result

21322 - Sophia - Chemistry
21477 - Andrew - Biology
21507 - John - Mathematics
21905 - James - Physics

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

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

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