Experience Programmers

mt106250 (28)


Below is C code for the merge sort algorithm. Programmers it is your job to produce a main.c that tests the functionality of the mergeSort library and to explain exactly what the code is doing under different test cases.

how void recMergeSort(struct node** head) works. You need to describe each line of the function for four of your test cases you have.

recMergeSort makes a call to divideList, 2 recursive calls to itself, recMergeSort, and a call to mergeList, you must describe what happens in these 4 function calls. For the recursive calls, you must label the depth and which recursive call (first or second) that you are describing or drawing the picture for.

This main.c must have at least 10 test cases

merge.h
1
2
3
4
5
6
7
8
9
 
  struct node {
int info;
   struct node *next;
};
void divideList(struct node *,struct node **);
struct node * mergeList(struct node *,struct node *);
void recMergeSort(struct node **);
void mergeSort(struct node **, struct node **);


merge.c
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
  void divideList(struct node* first1,struct node** first2) {
   struct node* middle;
   struct node* current;
   if (first1 == NULL)  //list is empty
      *first2 = NULL;
   else if (first1->next == NULL)  //list has only one node
      *first2 = NULL;
   else
{
   middle = first1;
   current = first1->next;
   if (current != NULL)
                      //list has more than two nodes
current = current->next;
      while (current != NULL)
      {
         middle = middle->next;
         current = current->next;
         if (current != NULL)
            current = current->next;
      } //end while
      *first2 = middle->next;
      middle->next = NULL;
   } //end else
} //end divideList
struct node* mergeList(struct node* first1,struct node* first2)
{
   struct node *lastSmall; //pointer to the last node
   struct node *newHead;  //pointer to the merged list
   if (first1 == NULL)  //the first sublist is empty
      return first2;
   else if (first2 == NULL)  //the second sublist is empty
      return first1;
else {
      if (first1->info < first2->info) //compare the first nodes
      {
         newHead = first1;
         first1 = first1->next;
         lastSmall = newHead;
} else {
         newHead = first2;
         first2 = first2->next;
         lastSmall = newHead;
      }
      while (first1 != NULL && first2 != NULL)
      {
         if (first1->info < first2->info)
         {
            lastSmall->next = first1;
            lastSmall = lastSmall->next;
            first1 = first1->next;
} else {
            lastSmall->next = first2;
            lastSmall = lastSmall->next;
            first2 = first2->next;
         }
      } //end while
      if (first1 == NULL) //first sublist is exhausted first
         lastSmall->next = first2;
      else      //second sublist is exhausted first
         lastSmall->next = first1;
      return newHead;
   }
}//end mergeList
void recMergeSort(struct node** head)
{
   struct node* otherHead;
   if (*head != NULL)  //if the list is not empty
      if ((*head)->next != NULL)  //if list has more than one
      {
         divideList(*head, &otherHead);
         recMergeSort(head);
         recMergeSort(&otherHead);
         *head = mergeList(*head, otherHead);
      }
} //end recMergeSort
void mergeSort(struct node **first, struct node **last)
{
   recMergeSort(first);
   if (*first == NULL)
      *last = NULL;
else {
      *last = *first;
      while ((*last)->next != NULL)
      *last = (*last)->next;
   }
} //end mergeSort
keskiverto (10399)
Smells like homework.
Programmers it is your job ...

I do assume that by "programmers" you do mean user mt106250. Your job.
Topic archived. No new replies allowed.