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:
 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;
}
}
4 answers

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

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. 
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 linkedlist, copy the entire linkedlist 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 nontrivial setup time. However, it's also very idiomatic. You could also allocate an array of pointers,
qsort
it, and use the pointers as markers while reindexing. 
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 thenum_id
member with the next is different from the condition for doing the same withname
. 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, yourpush_data
already has the logic to put a node in front of the list when itsnum_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.
do you know?
how many words do you know