1. Please copy-and-paste the following files (0 Points):

   insertionSort.c

   /*--------------------------------------------------------------------------* *---- ----* *---- insertionSort.c ----* *---- ----* *---- This file defines a function that implements insertion ----* *---- sort on a linked-list of integers. ----* *---- ----* *---- ---- ---- ---- ---- ---- ---- ---- ---- ----* *---- ----* *---- Version 1a Joseph Phillips ----* *---- ----* *--------------------------------------------------------------------------*/ #include "headers.h" // PURPOSE: To sort the linked-list of nodes pointed to by 'nodePtr' using // the insertion sort algorithm. Returns the first node of the sorted // list. struct Node* insertionSort (struct Node* nodePtr ) { struct Node* startPtr = NULL; struct Node* endPtr = NULL; struct Node* lowestPtr; struct Node* lowestPrevPtr; while (nodePtr != NULL) { struct Node* prevPtr; struct Node* run; lowestPrevPtr = NULL; lowestPtr = nodePtr; for (prevPtr = nodePtr, run = nodePtr->nextPtr_; run != NULL; prevPtr = run, run = run->nextPtr_ ) { if (lowestPtr->value_ > run->value_) { lowestPtr = run; lowestPrevPtr = prevPtr; } } if (lowestPrevPtr == NULL) { if (startPtr == NULL) { startPtr = endPtr = lowestPtr; } else { endPtr->nextPtr_ = lowestPtr; endPtr = endPtr->nextPtr_; } nodePtr = nodePtr->nextPtr_; endPtr->nextPtr_ = NULL; } else { if (startPtr == NULL) { startPtr = endPtr = lowestPtr; } else { endPtr->nextPtr_ = lowestPtr; endPtr = endPtr->nextPtr_; } lowestPrevPtr->nextPtr_ = lowestPtr->nextPtr_; endPtr->nextPtr_ = NULL; } } print(startPtr); return(startPtr); } 

   mergeSort.c

   /*--------------------------------------------------------------------------* *---- ----* *---- mergeSort.c ----* *---- ----* *---- This file defines a function that implements merge-sort on ----* *---- a linked-list of integers. ----* *---- ----* *---- ---- ---- ---- ---- ---- ---- ---- ---- ----* *---- ----* *---- Version 1a Joseph Phillips ----* *---- ----* *--------------------------------------------------------------------------*/ #include "headers.h" // PURPOSE: To sort the linked-list of nodes pointed to by 'nodePtr' using // the merge sort algorithm. Returns the first node of the sorted list. struct Node* mergeSort (struct Node* nodePtr ) { if ( (nodePtr == NULL) || (nodePtr->nextPtr_ == NULL) ) { return(nodePtr); } struct Node* run; struct Node* run2; struct Node* lastPtr = NULL; for ( run = run2 = nodePtr; (run2 != NULL) && (run2->nextPtr_ != NULL); lastPtr = run, run = run->nextPtr_, run2 = run2->nextPtr_->nextPtr_ ); lastPtr->nextPtr_ = NULL; run2 = mergeSort(run); run = mergeSort(nodePtr); nodePtr = NULL; lastPtr = NULL; while ( (run != NULL) && (run2 != NULL) ) { if (run->value_ < run2->value_) { if (nodePtr == NULL) { nodePtr = lastPtr = run; } else { lastPtr = lastPtr->nextPtr_ = run; } run = run->nextPtr_; } else { if (nodePtr == NULL) { nodePtr = lastPtr = run2; } else { lastPtr = lastPtr->nextPtr_ = run2; } run2 = run2->nextPtr_; } } if (run == NULL) { if (lastPtr == NULL) { nodePtr = run2; } else { lastPtr->nextPtr_ = run2; } } else { if (lastPtr == NULL) { nodePtr = run; } else { lastPtr->nextPtr_ = run; } } return(nodePtr); } struct Node* mergeSortWrapper(struct Node* nodePtr ) { nodePtr = mergeSort(nodePtr); print(nodePtr); return(nodePtr); } 

2. C programming (20 Points):

   These two files need a main() to run their functions insertionSort() and mergeSortWrapper(). Then all three C files need a header file to inform them of what the others have that they need, including Node.h which defines the data-structure. Please finish both the main.c and headers.h

   • Please make print() print the whole linked list.
   • For headers.h, not everything needs to be shared.
     • main() needs insertionSort() and mergeSortWrapper()
     • Both insertionSort() and mergeSortWrapper() need print().
     Otherwise, it is best not to share too much, kind of like keeping methods and members private in C++ and Java.

   headers.h

   /*--------------------------------------------------------------------------* *---- ----* *---- headers.h ----* *---- ----* *---- This file declares common headers used through-out the ----* *---- the singly-linked list sorting program. ----* *---- ----* *---- ---- ---- ---- ---- ---- ---- ---- ---- ----* *---- ----* *---- Version 1a Joseph Phillips ----* *---- ----* *--------------------------------------------------------------------------*/ #include  #include  #include "Node.h" // YOUR CODE HERE 

   Node.h

   /*--------------------------------------------------------------------------* *---- ----* *---- Node.h ----* *---- ----* *---- This file declares the struct that stores an integer and ----* *---- a next-pointer to implement a node in a singly-linked list. ----* *---- ----* *---- ---- ---- ---- ---- ---- ---- ---- ---- ----* *---- ----* *---- Version 1a Joseph Phillips ----* *---- ----* *--------------------------------------------------------------------------*/ struct Node { int value_; struct Node* nextPtr_; }; 

   main.c

   /*--------------------------------------------------------------------------* *---- ----* *---- main.c ----* *---- ----* *---- This file defines the main functions for a program that ----* *---- sorts a linked list of randomly-generated integers. ----* *---- ----* *---- ---- ---- ---- ---- ---- ---- ---- ---- ----* *---- ----* *---- Version 1a Joseph Phillips ----* *---- ----* *--------------------------------------------------------------------------*/ #include "headers.h" #define TEXT_LEN 256 #define NUM_NUMBERS (2*65536) int numNumbers = NUM_NUMBERS; // PURPOSE: To create and return the address of the first node of a linked // list of 'length' struct Node instances, each with a randomly-generated // integer in its 'value_' member variable. struct Node* createList (int length ) { if (length == 0) { return(NULL); } struct Node* startPtr = (struct Node*)malloc(sizeof(struct Node)); struct Node* endPtr = startPtr; startPtr->value_ = rand() % 4096; startPtr->nextPtr_ = NULL; for (length--; length > 0; length--) { endPtr->nextPtr_ = (struct Node*)malloc(sizeof(struct Node)); endPtr->nextPtr_->value_ = rand() % 4096; endPtr->nextPtr_->nextPtr_ = NULL; endPtr = endPtr->nextPtr_; } return(startPtr); } // PURPOSE: To print integer values in the linked list pointed to by // 'nodePtr'. No return value. void print (const struct Node* nodePtr ) {  // YOUR CODE HERE } // PURPOSE: To 'free()' the 'struct Node' instances of the linked list // pointed to by 'nodePtr'. No return value. void freeList (struct Node* nodePtr ) { struct Node* nextPtr; for ( ; nodePtr != NULL; nodePtr = nextPtr) { nextPtr = nodePtr->nextPtr_; free(nodePtr); } } // PURPOSE: To run this program. Ignores command line arguments. Returns // 'EXIT_SUCCESS' to OS. int main () { int choice; struct Node* nodePtr = createList(numNumbers); print(nodePtr); do { char text[TEXT_LEN]; printf ("How do you want to sort %d numbers? " "(1) Insertion sort " "(2) Merge sort " "Your choice (1 or 2)? ", NUM_NUMBERS ); fgets(text,TEXT_LEN,stdin); choice = strtol(text,NULL,10); } while ( (choice < 1) || (choice > 2) ); switch (choice) { case 1 : nodePtr = insertionSort(nodePtr); break; case 2 : nodePtr = mergeSortWrapper(nodePtr); break; } freeList(nodePtr); return(EXIT_SUCCESS); }