Hello, The following is a working function for sorting a linked list in C via in

Question

Hello,

The following is a working function for sorting a linked list in C via insertion sort. I am looking for a good explanation as to why this code works. Can someone please resubmit this to me with comments next to the code lines to explain exactly what the code is doing and why this algorithm works? I am familiar with structs and typedefs - no need to explain that... I am just looking for the logic as to how the code knows to compare the node links and their data and such... Thank you very much.

// function to sort a singly linked list using insertion sort
void sort() {
   Node *current1 = head->link;
   Node *pre1 = head;
   Node *current2= head;
   Node *pre2= head;

   while(NULL != current1) {
       pre2 = head;
       current2 = head;

       while((current2->data < current1->data)) {
           pre2 = current2;
           current2 = current2->link;
       }
       if(current2 != current1) {
           pre1->link = current1->link;
           if(current2 == head) {
               current1->link = head;
               head = current1;
           }
           else {
               pre2->link = current1;
               current1->link = current2;
           }
           current1 = pre1->link;
       }
       else {
           pre1 = pre1->link;
           current1 = current1->link;
       }
   }
}

Explanation / Answer

// Explained in detail of how the code works with inline comments

void sort() {
   // current node contains the data and link of the node pointed by heads link
Node *current1 = head->link;
  
   // pre1 contains data and link of the head; (pre1->link = head->link; pre1->data = head->data )
Node *pre1 = head;
  
   // current2 contains data and link of the head; (current2->link = head->link; current2->data = head->data )
Node *current2= head;   
  
   // pre2 contains data and link of the head; (pre2->link = head->link; pre2->data = head->data )
Node *pre2= head;   
  
   // Checks if the current1 is null, if null then it is the end of the list;
   // Ex: If head is only element in the list then head->link is null; As current1 = head->link, current1 contains null, then list is sorted
while(NULL != current1) {

       // pre2 contains data and link of the head; (pre2->link = head->link; pre2->data = head->data )
pre2 = head;
      
       // current2 contains data and link of the head; (current2->link = head->link; current2->data = head->data )
current2 = head;
      
      
       // compares data of current2 node and current1 node, if current2->data < current1->data then both elements are sorted already
       // Move to next node untill current2->data > current1->data
while((current2->data < current1->data)) {   
      
           // pre2 contains current2
pre2 = current2;
          
           // current2 moves to next node
current2 = current2->link;   
}
      
      
       // If current2 is not current 1
if(current2 != current1) {
pre1->link = current1->link;
          
           // Compare current node with before nodes
if(current2 == head) {
current1->link = head;
head = current1;
}
          
           //Swap the nodes as current2->data > current1->data
           // Swap current2 and current1 nodes using pre2
           // Before swapping current2 -> link points to current1
           // After swapping current1 link points to current2
           // Ex: if pre2 -> link = current2; current2 -> link = current1, then directly point pre2->link = current1; current1->link = current2;
else {
pre2->link = current1;
current1->link = current2;
}
current1 = pre1->link;
}
      
       //If current2 == current1
else {
      
           // Move pre1 to next node pointed by pre1 itself (pre1->link)
pre1 = pre1->link;
          
           // Move current1 to next node pointed by current1 itself
current1 = current1->link;
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.