CODEWITHSUNDEEP
clistsortingdata-structuresmergesort
user2675010
user2675010

Reputation:

Nested Merge sort in C not working

I have a linked list node as: 

typedef struct Record{
  char name[100];
  int branch_id;
  struct Record *next;
}record;

What I want to do is first sort the linked list on the name and for the same name sort it for the branch_id. But it's only sorting on the name. What am I doing wrong here? 

record *merge_sort( record * );
record *divide(record *);
record *merge(record *,record *);  

record *merge_sort( record *p )
{
  record *q;
  record *head=p;
  if(p!=NULL && p->next!=NULL){
    q=divide(p);
    p=merge_sort(p);
    q=merge_sort(q);
    head=merge(p,q);
  }
  return head;
}

record *divide(record *p)
{
  record *q,*r;
  q=p;
  r=p->next->next;
  while(r!=NULL){
    r=r->next;
    q=q->next;
    if(r!=NULL){
      r=r->next;
    }
  }
  r=q;
  q=q->next;
  r->next=NULL;
  return q;
}

record *merge(record *p,record *q)
{
  record *head,*tail;
  if(p==NULL || q==NULL){
    printf("Both the sub elements are empty\n");
  }
  if(strcmp(p->name,q->name)<0){
    head=p;
    p=p->next;
  }
  else if((strcmp(p->name,q->name)==0) && (p->branch_id < q->branch_id)){
    head=p;
    p=p->next;
  }
  else if((strcmp(p->name,q->name)==0) && (p->branch_id > q->branch_id)){
    head=q;
    q=q->next;
  }
  else{
    head=q;
    q=q->next; 
  }
  tail=head;
  while(p!=NULL && q!=NULL){
    if(strcmp(p->name,q->name)<0){
      tail->next=p;
      tail=p;
      p=p->next;
    }
    else if((strcmp(p->name,q->name)==0) && (p->branch_id < q->branch_id)){
      tail->next=p;
      tail=p;
      p=p->next;
    }
    else if((strcmp(p->name,q->name)==0) && (p->branch_id > q->branch_id)){
      tail->next=p;
      tail=p;
      p=p->next;
    }
    else{
      tail->next=q;
      tail=q;
      q=q->next;
    }
  }
  if(p!=NULL){
    tail->next=p;
  }
  else{
    tail->next=q;
  }
  return head;
}

Upvotes: 3

Views: 86

Answers (1)

Iwillnotexist Idonotexist
Iwillnotexist Idonotexist

Reputation: 13467

In merge(), specifically in

while(p!=NULL && q!=NULL){
  if(strcmp(p->name,q->name)<0){
    tail->next=p;
    tail=p;
    p=p->next;
  }
  else if((strcmp(p->name,q->name)==0) && (p->branch_id < q->branch_id)){
    tail->next=p;
    tail=p;
    p=p->next;
  }
  else if((strcmp(p->name,q->name)==0) && (p->branch_id > q->branch_id)){
    tail->next=p;
    tail=p;
    p=p->next;
  }
  else{
    tail->next=q;
    tail=q;
    q=q->next;
  }
}

The second and third case's code is identical, assigning p to tail . However, in the loop header, I see that for the third case you're assigning q. Maybe you missed it while copy-pasting the loop header?

Can I also advise that you implement a function? It seems like a good factoring and would have prevented this error.

int reccmp(record *p,record *q){
    int ret = strcmp(p->name,q->name), diff;

    if(!ret){
        diff = p->branch_id > q->branch_id;

        ret = diff < 0 ? -1 : (diff > 0 ? 1 : 0);
    }

    return ret;
}

Upvotes: 4

Related Questions