Assignment 7

---

[ Submission site  |  Show solution  |  Hide solution ]

---

In this assignment you are asked to implement merge sort on linked lists. The essential idea is described in the following figure.

We use the following type definitions. We maintain the size of a list in the list header. Maintaining the size field eliminates the need for computing the size of a list on the fly by traversing the list from the beginning to the end.

   typedef struct _node {
      int key;             /* The key value to be stored in a node */
      struct _node *next;  /* Pointer to the next node */
   } node;

   typedef struct {
      unsigned int size;   /* Number of elements in the list */
      node *first;         /* Pointer to the first element in the list */
   } list;

I provide you two functions, one for creating a random list of n elements, and the other for printing the elements in a list from beginning to end.

Part 1 [Credit: 50%]

Write a merging function that accepts two list headers as arguments, and returns a header to the merged list. The input lists are assumed to be sorted. No fresh memory allocation is to be made inside this function. Only the pointers in the input lists are to be rearranged so as to produce the merged sorted list.

   list merge ( list L1, list L2 );

Part 2 [Credit: 50%]

Write a function that implements the merge sort algorithm described in the above figure. The function accepts a header to the list to be sorted. The merge sort function first breaks the list in two (almost) equal halves. The two halves are pointed to by L1 and L2. Two recursive calls are then made in order to sort the lists headed by L1 and L2. The resulting sorted sublists are merged using the merge function of Part 1. Do not make fresh memory allocation to produce the two sublists. Just break the input list in two halves by adjusting an appropriate pointer near the center of the input list.

   list mergeSort ( list L );

Download the skeleton of the program

Report the output of your program on a list of size 200.

Sample output

Enter size of list : 40
Original list :  741 188 947 559 542 430 253 357 143 257 605 314 921 670
 227 151 715 559 241 897 184 977 981 850  11 372 725 346 949 737 264 690
 277 212 602 171 994 855 528 137
Sorted list   :   11 137 143 151 171 184 188 212 227 241 253 257 264 277
 314 346 357 372 430 528 542 559 559 602 605 670 690 715 725 737 741 850
 855 897 921 947 949 977 981 994

---

Solution

Source code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 1000

typedef struct _node {
   int key;
   struct _node *next;
} node;

typedef struct {
   unsigned int size;
   node *first;
} list;

list initList ( unsigned int n )
{
   list L;
   node *p;
   int i;

   L.size = n;
   if (n == 0) L.first = NULL;
   else {
      p = L.first = (node *)malloc(sizeof(node));
      p -> key = rand() % MAX;
      for (i=1; i<n; ++i) {
         p -> next = (node *)malloc(sizeof(node));
         p = p -> next;
         p -> key = rand() % MAX;
      }
      p -> next = NULL;
   }
   return L;
}

void printList ( list L )
{
   unsigned int i;
   node *p;
   int ncp = 4;

   if (L.size > 0) {
      p = L.first;
      for (i=0; i<L.size; ++i) {
         printf("%4d", p -> key);
         p = p -> next;
         if (++ncp == 18) {
            printf("\n");
            ncp = 0;
         }
      }
   }
   if (ncp) printf("\n");
}

list merge ( list L1, list L2 )
{
   list L;
   node *p, *q, *r;

   if (L1.size == 0) return L2;
   if (L2.size == 0) return L1;
   L.size = L1.size + L2.size;
   p = L1.first;
   q = L2.first;
   if (p -> key < q -> key) {
      r = L.first = L1.first;
      p = p -> next;
   } else {
      r = L.first = L2.first;
      q = q -> next;
   }
   while ((p != NULL) && (q != NULL)) {
      if (p -> key < q -> key) {
         r -> next = p;
         p = p -> next;
      } else {
         r -> next = q;
         q = q -> next;
      }
      r = r -> next;
   }
   r -> next = (p != NULL) ? p : q;
   return L;
}

list mergeSort ( list L )
{
   list L1, L2;
   node *p;
   unsigned int i, n;

   n = L.size;

   /* Termination condition */
   if (n <= 1) return L;

   /* Break the list in two parts: first to be headed by L1, second by L2 */
   L1 = L;
   L1.size = n/2;
   L2.size = (n+1)/2;
   p = L.first;
   for (i=1; i<L1.size; ++i) p = p -> next;
   L2.first = p -> next;
   p -> next = NULL;

   /* Recursive calls */
   L1 = mergeSort(L1);
   L2 = mergeSort(L2);

   /* Merge two sorted lists */
   L = merge(L1,L2);
   return L;
}

int main ()
{
   unsigned int n;
   list L;

   srand((unsigned int)time(NULL));
   printf("Enter size of list : "); scanf("%u", &n); printf("%u\n", n);
   L = initList(n);
   printf("Original list : "); printList(L);
   L = mergeSort(L);
   printf("Sorted list   : "); printList(L);
}

Sample output

Enter size of list : 200
Original list :   38 466 306  44 108 709 553 487 168 998 136 158 566 562
 976 390 730 830 389 821 383 347 913 909 810 328 580 912 835 197 729 225
 663 387 269 772  96 822 259 617 172 747 775 738 309 103 128  39 285 517
 213  20 217 126 929 379 806 510 643 641  59 372 866 722 111 487 846 208
 309 457 825 481 204 952 220 513 407 700 905  44 570 118 416 787 596 698
 166 402 208 809 396 267 533 614 341 644 102 188 204 411 645 381 245 202
 685 465 715 444 517 972 488  87  90 905 874 686 955 392 441 163 553 189
 782 438 803 475 435 257  15 639  21  13 373 266 215  58  83 282 503 600
 255 343 688 345 600 914 384 555 307 825  70 212  14 852 651 169 680  86
 427 695  77 448 708 450 714 923 861 149 206 364 749 461 707 789 158 660
 704 542 215 363 367 286 575 733 490 578 903 170  16 682 866  94 130 926
 544 196 850 405 345 408
Sorted list   :   13  14  15  16  20  21  38  39  44  44  58  59  70  77
  83  86  87  90  94  96 102 103 108 111 118 126 128 130 136 149 158 158
 163 166 168 169 170 172 188 189 196 197 202 204 204 206 208 208 212 213
 215 215 217 220 225 245 255 257 259 266 267 269 282 285 286 306 307 309
 309 328 341 343 345 345 347 363 364 367 372 373 379 381 383 384 387 389
 390 392 396 402 405 407 408 411 416 427 435 438 441 444 448 450 457 461
 465 466 475 481 487 487 488 490 503 510 513 517 517 533 542 544 553 553
 555 562 566 570 575 578 580 596 600 600 614 617 639 641 643 644 645 651
 660 663 680 682 685 686 688 695 698 700 704 707 708 709 714 715 722 729
 730 733 738 747 749 772 775 782 787 789 803 806 809 810 821 822 825 825
 830 835 846 850 852 861 866 866 874 903 905 905 909 912 913 914 923 926
 929 952 955 972 976 998

---

[ Submission site  |  Show solution  |  Hide solution ]

---

Back  |  Home