C++

Forum

 
Merge Sorting with Linked list

ayraj (1)
I done my project to add subjects and sort them.Im trying to sort them with merge sort but still its complicated for me. Pls help me with this.

This is my structure Subject:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
typedef struct subject
{
	int scredhours;
	char scode[30];
	char sname[30];
	int syear;
	char sdate[30];
	char stime[30];
	struct subject *slink;
}snode;

snode *sheader=NULL;
snode *sget_node()
{
	return((snode *)malloc(sizeof(snode)));
}

And this my Merge sorting Algorithms:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
void split(snode *head, snode **front, snode **back){

  snode *fast = head->slink;
  snode *slow = head;

  while(fast){
	fast = fast->slink;
	if(fast){
	  fast = fast->slink;
	  slow = slow->slink;
	}
  }
  *front = head;
  *back = slow->slink;
  slow->slink = NULL;
}
snode *merge(snode *a, snode *b){
 snode *result = NULL;
 if(a ==  NULL)
   return b;
 else if(b == NULL)
    return a;

 /* For the first node, we would set the result to either a or b */
 for(a=sheader;a!=NULL;a=a->slink){
        for(b=a->slink;b!=NULL;b=b->slink){
  if(a->scredhours <= b->scredhours){
    result = a;
    /* Result's next will point to smaller one in lists
    starting at a->next  and b */
    result->slink = merge(a->slink,b);
   }
   else {
    result = b;
    /*Result's next will point to smaller one in lists
    starting at a and b->next */
    result->slink = merge(a,b->slink);
   }
   return result;}}
}
void mergeSort(snode **headRef){
  snode * front, *back;
  snode * head  = *headRef;
  head = sheader;
  if(head == NULL || head->slink == NULL)
	return;
  split(head, &front, &back);
  mergeSort(&front);
  mergeSort(&back);
  *headRef = merge(front, back);
}
Last edited on
ne555 (10692)
> but still its complicated for me
you need to be more descriptive of the problem.
try with your dog first* (I'm serious).

1
2
 
  snode * head  = *headRef;
  head = sheader;
explain your reasoning, please.
First you set `head' to `headRef', then you just overwrite that value. In the end, you don't even use the parameter.
Same thing in `merge()', lines 25,26 
1
2
 
for(a=sheader;a!=NULL;a=a->slink){
        for(b=a->slink;b!=NULL;b=b->slink){
`a' and `b' were pointing to the list that you were working on, but you simply decided to throw away them.

Also, `sheader' is a global variable, ¿why?

* cats don't pay attention.
keskiverto (10363)
Look at the code sample under "The behavior of this function template is equivalent to" in:
http://www.cplusplus.com/reference/algorithm/merge/

It is a bit different, so it might give you new ideas.
Topic archived. No new replies allowed.