Reputation:
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
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