sort.txt

It is an ebook about data structures,mainly linked list

How do you sort a linked list? Write a C program to sort a linked list. 

Discuss it!          




This is a very popular interview question, which most people go wrong. The ideal solution to this problem is to keep the linked list sorted as you build it. Another question on this website teaches you how to insert elements into a linked list in the sorted order. This really saves a lot of time which would have been required to sort it. 


However, you need to Get That Job.... 



Method1 (Usual method) 

The general idea is to decide upon a sorting algorithm (say bubble sort). Then, one needs to come up with different scenarios to swap two nodes in the linked list when they are not in the required order. The different scenarios would be something like 


1. When the nodes being compared are not adjacent and one of them is the first node. 
2. When the nodes being compared are not adjacent and none of them is the first node 
3. When the nodes being compared are adjacent and one of them is the first node. 
4. When the nodes being compared are adjacent and none of them is the first node. 


One example bubble sort for a linked list goes like this (working C code!).... 




#include<stdio.h> 
#include<ctype.h> 

typedef struct node 
{ 
  int value; 
  struct node *next; 
  struct node *prev; 
}mynode ; 

void add_node(struct node **head, int *count, int value); 
void print_list(char *listName, struct node *head); 
mynode *bubbleSort(mynode *head, int count); 


int main() 
{ 
mynode *head; 
int count = 0; 

head = (struct node *)NULL; 

add_node(&head, &count, 100); 
add_node(&head, &count, 3); 
add_node(&head, &count, 90); 
add_node(&head, &count, 7); 
add_node(&head, &count, 9); 

print_list("myList(BEFORE)", head); 
head = bubbleSort(head, count); 
print_list("myList(AFTER) ", head); 


getch(); 
return(0); 

} 


mynode *bubbleSort(mynode *head, int count) 
{ 
  int i, j; 
  mynode *p0, *p1, *p2, *p3; 
   
  for(i = 1; i < count; i++) 
  { 
    p0 = (struct node *)NULL; 
    p1 = head; 
    p2 = head->next; 
    p3 = p2->next; 
   
    for(j = 1; j <= (count - i); j++) 
    { 
       if(p1->value > p2->value)   
       { 
           // Adjust the pointers...        
           p1->next = p3; 
           p2->next = p1; 
           if(p0)p0->next=p2; 
            

           // Set the head pointer if it was changed... 
           if(head == p1)head=p2; 


           // Progress the pointers 
           p0 = p2; 
           p2 = p1->next; 
           p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL; 

       } 
       else 
       { 
          // Nothing to swap, just progress the pointers... 
          p0 = p1; 
          p1 = p2; 
          p2 = p3; 
          p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL; 
       } 
    } 
  } 

  return(head); 
} 


void add_node(struct node **head, int *count, int value) 
{ 
  mynode *temp, *cur; 
  temp = (mynode *)malloc(sizeof(mynode)); 
  temp->next=NULL; 
  temp->prev=NULL; 

  if(*head == NULL) 
  { 
     *head=temp; 
     temp->value=value; 
  } 
  else 
  { 
   for(cur=*head;cur->next!=NULL;cur=cur->next); 
   cur->next=temp; 
   temp->prev=cur; 
   temp->value=value; 
  } 
   
  *count = *count + 1; 
} 


void print_list(char *listName, struct node *head) 
{ 
  mynode *temp; 

  printf("\n[%s] -> ", listName); 
  for(temp=head;temp!=NULL;temp=temp->next) 
  { 
    printf("[%d]->",temp->value); 
  } 
   
  printf("NULL\n"); 

} 



As you can see, the code becomes quite messy because of the pointer logic. Thats why I have not elaborated too much on the code, nor on variations such as sorting a doubly linked list. You have to do it yourself once to understand it. 






Method2 (Divide and Conquer using Merge Sort) 


Here is some cool working C code... 



#include<stdio.h> 
#include<ctype.h> 

typedef struct node 
{ 
  int value; 
  struct node *next; 
  struct node *prev; 
}mynode ; 



void add_node(struct node **head, int value); 
void print_list(char *listName, struct node *head); 
void mergeSort(struct node** headRef); 
struct node *merge2SortedLLs(struct node *head1, struct node *head2); 
void splitLLInto2(struct node* source, struct node** frontRef, struct node** backRef); 


// The main function.. 
int main() 
{ 
   mynode *head; 
   head = (struct node *)NULL; 

   add_node(&head, 1); 
   add_node(&head, 10); 
   add_node(&head, 5); 
   add_node(&head, 70); 
   add_node(&head, 9); 
   add_node(&head, -99); 
   add_node(&head, 0); 


   print_list("myList", head); 
   mergeSort(&head); 
   print_list("myList", head); 

   getch(); 
   return(0); 
} 




// This is a recursive mergeSort function... 
void mergeSort(struct node** headRef) 
{ 
  struct node* head = *headRef; 
  struct node* a; 
  struct node* b; 

  // Base case -- length 0 or 1 
  if ((head == NULL) || (head->next == NULL)) 
  { 
    return; 
  } 
   
  // Split head into 'a' and 'b' sublists 
  splitLLInto2(head, &a, &b); 

  // Recursively sort the sublists 
  mergeSort(&a); 
  mergeSort(&b); 

  // Merge the two sorted lists together 
  *headRef = merge2SortedLLs(a, b); 
} 





// This is an iterative function that joins two already sorted 
// Linked lists... 
struct node *merge2SortedLLs(struct node *head1, struct node *head2) 
{ 
   struct node *a, *b, *c, *newHead, *temp; 
    
   a = head1; 
   b = head2; 
   c       = (struct node *)NULL; 
   newHead = (struct node*)NULL; 
    
    
   if(a==NULL)return(b); 
   else if(b==NULL)return(a); 
    
   while(a!=NULL && b!=NULL) 
   { 
     if(a->value < b->value) 
     { 
       //printf("\na->value < b->value\n"); 
       if(c==NULL) 
       { 
         c  = a; 
       } 
       else 
       { 
         c->next = a; 
         c = c->next; 
       } 
       a  = a->next;     
     } 
     else if(a->value > b->value) 
     { 
       //printf("\na->value > b->value\n"); 
       if(c==NULL) 
       { 
         c  = b; 
       } 
       else 
       { 
         c->next = b; 
         c = c->next; 
       } 
       b  = b->next; 
     } 
     else 
     { 
       // Both are equal. 
       // Arbitraritly chose to add one of them and make 
       // sure you skip both! 

       if(c == NULL) 
       { 
         c  = a; 
       } 
       else 
       { 
         c->next = a; 
         c = c->next; 
       } 
        
       a  = a->next; 
       b  = b->next; 
     } 
      
     // Make sure the new head is set... 
     if(newHead == NULL) 
      newHead = c; 
    
   } 
    
   if(a==NULL && b==NULL) 
     return(newHead); 
      
   if(a==NULL) 
     c->next = b; 
   else if(b==NULL) 
     c->next = a; 
      
   return(newHead); 
    
} 


// Uses the fast/slow pointer strategy 
// 
// This efficient code splits a linked list into two using 
// the same technique as the one used to find the 
// middle of a linked list! 

void splitLLInto2(struct node* source, struct node** frontRef, struct node** backRef) 
{ 
  struct node* fast; 
  struct node* slow; 
   
  if (source==NULL || source->next==NULL) 
  { 
    // length < 2 cases 
    *frontRef = source; 
    *backRef = NULL; 
  } 
  else 
  { 
    slow = source; 
    fast = source->next; 
    // Advance 'fast' two nodes, and advance 'slow' one node 
    while (fast != NULL) 
    { 
       fast = fast->next; 
       if (fast != NULL) 
       { 
          slow = slow->next; 
          fast = fast->next; 
       } 
    } 
    // 'slow' is before the midpoint in the list, so split it in two 
    // at that point. 
    *frontRef = source; 
    *backRef = slow->next; 
    slow->next = NULL; 
  } 
} 


void add_node(struct node **head, int value) 
{ 
  mynode *temp, *cur; 
  temp = (mynode *)malloc(sizeof(mynode)); 
  temp->next=NULL; 
  temp->prev=NULL; 

  if(*head == NULL) 
  { 
     *head=temp; 
     temp->value=value; 
  } 
  else 
  { 
   for(cur=*head;cur->next!=NULL;cur=cur->next); 
   cur->next=temp; 
   temp->prev=cur; 
   temp->value=value; 
  } 
} 


void print_list(char *listName, struct node *head) 
{ 
  mynode *temp; 

  printf("\n[%s] -> ", listName); 
  for(temp=head;temp!=NULL;temp=temp->next) 
  { 
    printf("[%d]->",temp->value); 
  } 
   
  printf("NULL\n"); 

} 



The code to merge two already sorted sub-linked lists into a sorted linked list could be either iterative or recursive. You already saw the iterative version above. Here is a recursive version of the same... 


Recursive solution to merge two already sorted linked lists into a single linked list 




struct node* sortedMergeRecursive(struct node* a, struct node* b) 
{ 
  struct node* result = NULL; 

  if (a==NULL) return(b); 
  else if (b==NULL) return(a); 

  // Pick either a or b, and recur 
  if (a->data <= b->data) 
  { 
     result = a; 
     result->next = sortedMergeRecursive(a->next, b); 
  } 
  else 
  { 
     result = b; 
     result->next = sortedMergeRecursive(a, b->next); 
  } 
   
  return(result); 
} 




Also, see how the splitLLInto2() function uses the same technique used to find the middle of a linked list to split a linked list into two without having to keep a count of the number of nodes in the linkes list! 

Here is another solution (not that great, though) to split a linked list into two. It used the count of the number of nodes to decide where to split 


void splitLLInto2(struct node* source,struct node** frontRef, struct node** backRef) 
{ 
  int len = Length(source); //Get the length of the original LL.. 
  int i; 
  struct node* current = source; 
   
  if (len < 2) 
  { 
    *frontRef = source; 
    *backRef = NULL; 
  } 
  else 
  { 
     int hopCount = (len-1)/2; 

     for (i = 0; i<hopCount; i++) 
     { 
        current = current->next; 
     } 
      
     // Now cut at current 
    *frontRef = source; 
    *backRef = current->next; 
    current->next = NULL; 
  } 
} 



Using recursive stack space proportional to the length of a list is not recommended. However, the recursion in this case is ok ? it uses stack space which is proportional to the log of the length of the list. For a 1000 node list, the recursion will only go about 10 deep. For a 2000 node list, it will go 11 deep. If you think about it, you can see that doubling the size of the list only increases the depth by 1.