Sorting using linked list

Question

I have two fields namely ID and name. Upon inserting a node in a linked list, I would like to sort it by ID in descending order. Assuming that it is possible that different persons can have the same ID. For Example

1001 CHARICE -> 1001 JUSTIN -> 1001 ANNA -> 1000 CHYNA -> 888 MIKEY -> NULL

The final list should look like this:

1001 ANNA -> 1001 CHARICE -> 1001 JUSTINE -> 1000 CHYNA -> 888 MIKEY -> NULL

I sort the names with the same ID in ascending order while the IDs are sorted in descending order. Here is my code:

NODE* insert_std(NODE *head, NODE* std){
     NODE *prev, *cur;
     if(head==NULL) return std; 
     cur = head;
     while (cur != NULL &&  std->ID < cur->ID){  
         prev = cur;
         cur = cur->next;
     }
     if(std->ID == cur->ID){
         while (cur != NULL &&  strcmp(std->name, cur->name)>=0){
             prev = cur;
             cur = cur->next;
         }
     }    
     if (head==cur){
         if(std->ID >= head->ID) {
         std->next = head;
         head = std;
         }
     } else {
         std->next = cur;
         prev->next = std;
     }
     return head;
}

But is is not being sorted the way I want it. What am I doing wrong?

This one will be useful: en.wikipedia.org/wiki/Sentinel_node — ruslik
– ruslik, Commented Dec 15, 2010 at 17:38
Please find my solution for this problem using quick sort algo at <stackoverflow.com/questions/11813696/sorting-a-linked-list-in-c/…> — user1596193
– user1596193, Commented Mar 17, 2013 at 3:47

NPE · Accepted Answer · 2010-12-15 17:01:38Z

2

In your insertion function, whenever you compare two nodes, compare the two IDs first. If one is smaller than the other, this tells you which node should come first. If the IDs are the same, you need to compare the names to decide which node comes first.

This amounts to modifying std->ID <= cur->ID and std->ID > head->ID. If I were you, I would write a helper function that would take two pointers to NODE (call them A and B), compare them in the manner described above and return true if node A comes before node B. Incorporating this function into your insert_std is then trivial.

answered Dec 15, 2010 at 17:01

NPE

503k114 gold badges970 silver badges1k bronze badges

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

Comments

Frederik Slijkerman · Accepted Answer · 2010-12-15 17:02:53Z

2

Simply replace your comparisons on ID values, and take into account the name as well (for example using strcmp) when the ID values are the same. The easiest way is to write a separate function for comparing two records which does this job.

answered Dec 15, 2010 at 17:02

Frederik Slijkerman

6,55932 silver badges42 bronze badges

Comments

newbie · Accepted Answer · 2010-12-15 17:54:14Z

0

Add && std->ID == cur->ID on the while loop

 while (cur != NULL &&  std->ID == cur->ID && strcmp(std->name, cur->name)>=0)

answered Dec 15, 2010 at 17:54

newbie

15.1k33 gold badges108 silver badges149 bronze badges

Collectives™ on Stack Overflow

Sorting using linked list

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related