0

We have the following piece of a C program.I want to understand what this part of code does and its complexity.

void   sortLike          (node* p) 
        node* q;
        node* min;
        node *head = (struct node*) malloc (sizeof (struct node));
        head->next = L;
        p = head;

// We have to sort the list,obviously.We have the variable p and q which are pointer to node variables.We have determined the size of the head node.I dont understand what node* min and head->next = L; means.

        while (p->next->next!=NULL)
        {
            min = p;
            q = p->next;
            while (q->next!=NULL)
            {
                if (min->next->like < q->next->like)
                    min = q;
                q = q->next;

What does this block of code do? 

}
                node* a = p->next;
                p->next = min->next;
                min->next = a;
                node* b = a->next;
                a->next = p->next->next;
                p->next->next = b;
                p = p->next;
            }
            L = head->next;
        }

What about this one?

Question : What kind of sorting algorithm is this? I would guess it's selection sort.Whats its complexity?Can we turn this into a merge sort algorithm?

user3543012
  • 37
  • 4
  • What is L? Can you please show me it's declaration (which might be done in the earlier part of the program)? – Vikram Aug 27 '14 at 21:44

1 Answers1

0
void   sortLike          (node* p) 
        node* q;
        node* min;
        node *head = (struct node*) malloc (sizeof (struct node));
        head->next = L;
        p = head;

This allocates a sentinel node and inserts it at the beginning of the list. I probably would have allocated it on the stack (actually, I probably would have used pointers to pointers throughout, but that's off-topic). It also allocates some variables whose purpose is as yet unclear.

while (p->next->next!=NULL)
{
    min = p;
    q = p->next;
    while (q->next!=NULL)
    {
        if (min->next->like < q->next->like)
            min = q;
        q = q->next;

This part looks for the node having the minimum value of ->like, breaking ties in favor of later nodes (so this sort isn't stable). The meanings of p and min are a little funny: they point to the node before the beginning of the current sublist and the node before the minimum respectively. This is so that we can splice (next chunk; also explains why we needed the sentinel).

        node* a = p->next;
        p->next = min->next;
        min->next = a;
        node* b = a->next;
        a->next = p->next->next;
        p->next->next = b;
        p = p->next;
    }
    L = head->next;
}

This chunk moves min->next to the beginning of the list and moves p forward one, completing an implementation of selection sort for linked lists.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120