0

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;
    }
}
Improve this question
2
  • 3
    If you are sorting linked lists, what's with all the strcpy of data? That does not make any sense to me. Just reorder the nodes and don't touch the names. Commented Sep 11, 2021 at 20:11
  • 1
    By current->nim did you mean current->num_id? Commented Sep 11, 2021 at 20:18

4 Answers 4

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This increases the cost of push_data to O(n), but always keeping them in order is arguably much preferable, and probably fits the OP's use case.
Wow ! excellent, it solved now, so I just need to add some statement to my push_data, very good..
0

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.

Improve this answer

1 Comment

You are right with your explanation, but preferably you should present the correct code, too.
0

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.

Improve this answer

2 Comments

while(node) printf("No. %d; name: %s; lesson: %s.\n", node->num_id, node->name, node->lesson), node = node->link; <<-- what a terrible way to avoid a for() loop!
@wildplasser that is totally true; I'll fix that.
-1

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

Improve this answer

1 Comment

The geeks for geeks example is an inefficient top down merge sort. Just after explaining that linked lists are slow for random access, that is exactly what their code does in order to recursively split lists. A bottom up merge sort using a small array of pointers (26 to 32 entries) is more efficient.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.