[Solved] Final Part Assignment Write Several C Template Functions Sort List Items Using Recursive M Q37229889

For this final part of the assignment you will write several C++template functions to sort a list of items using the recursivemerge sort algorithm.

Program

Implement the following template functions in a header filecalled mergesort.h. This header file should have header guards (asusual) and should contain both the prototypes and definitions forthe functions.

• template <class T>
  void mergeSort(vector<T>& set, bool (*compare)(constT&, const T&))

  This function should sort the items in the vector set using themerge sort algorithm. The first argument to this function is areference to a vector object containing the list of items to sort.The second argument is a pointer to a comparison function that canbe used to compare two items of the template type.

  This function should call the recursive merge sort function,passing it the vector, the subscript of the first vector element(which is 0), the subscript of the last vector element (which isset.size() – 1), and the pointer to the comparison function(compare), e.g.:

  mergeSort(set, 0, set.size()-1, compare);

• template <class T>
  void mergeSort(vector<T>& set, int start, int end, bool(*compare)(const T&, const T&))

  This recursive function divides a vector into two subvectors,sorts them, and then merges the two sorted subvectors.

  int mid; if (start < end) { mid = (start + end) / 2; // Divide and conquer mergeSort(set, start, mid, compare); mergeSort(set, mid+1, end, compare); // Combine merge(set, start, mid, end, compare); } }

• template <class T>
  void merge(vector<T>& set, int start, int mid, int end,bool (*compare)(const T&, const T&))

  This function merges two sorted subvectors.

  // Create temporary vector to hold merged subvectors vector<T> temp(end – start + 1); int i = start; // Subscript for start of left sorted subvector int j = mid + 1; // Subscript for start of right sorted subvector int k = 0; // Subscript for start of merged vector // While not at the end of either subvector while (i <= mid && j <= end) { if (compare(set[i], set[j])) { Copy element i of set into element k of temp Add one to i Add one to k } else { Copy element j of set into element k of temp Add one to j Add one to k } } // Copy over any remaining elements of left subvector while (i <= mid) { Copy element i of set into element k of temp Add one to i Add one to k } // Copy over any remaining elements of right subvector while (j <= end) { Copy element j of set into element k of temp Add one to j Add one to k } // Copy merged elements back into original vector for (i = 0, j = start; j <= end; ++i, ++j) Copy element i of temp into element j of set

A driver program, assign8.cpp, is provided below to test yourcode for this part of the assignment. A copy of the driver programcan also be found on turing at/home/turing/t90kjm1/CS241/Code/Spring2019/Assign8/Part3/assign8.cpp.

/** * * CSCI 241 Assignment 8, Part 3 * * Author: your name * z-ID: your z-ID * Date: due date of assignment * * This program builds, sorts and prints lists using the quicksort and * merge sort algorithms. */#include <iostream>#include <iomanip>#include <vector>#include <string>#include “sorts.h”#include “quicksort.h”#include “mergesort.h”using std::cout;using std::fixed;using std::left;using std::setprecision;using std::string;using std::vector;// Data files#define D1 “/home/turing/t90kjm1/CS241/Data/Spring2019/Assign8/data8a.txt”#define D2 “/home/turing/t90kjm1/CS241/Data/Spring2019/Assign8/data8b.txt”#define D3 “/home/turing/t90kjm1/CS241/Data/Spring2019/Assign8/data8c.txt”// Output formatting constants#define INT_SZ 4 // width of integer#define FLT_SZ 7 // width of floating-pt number#define STR_SZ 12 // width of string#define INT_LN 15 // no of integers on single line#define FLT_LN 9 // no of floating-pt nums on single line#define STR_LN 5 // no of strings on single lineint main() { vector<int> v1; // vector of integers vector<float> v2; // vector of floating-pt nums vector<string> v3; // vector of strings // Print header message cout << “*** CSCI 241: Assignment 8 – Output ***nn”; // sort and print first list cout << “First list – ascending order:nn”; buildList(v1, D1); quickSort(v1, &lessThan); printList(v1, INT_SZ, INT_LN); v1.clear(); cout << “nFirst list – descending order:nn”; buildList(v1, D1); mergeSort(v1, &greaterThan); printList(v1, INT_SZ, INT_LN); // Sort and print second list cout << fixed << setprecision(2); cout << “nSecond list – descending order:nn”; buildList(v2, D2); quickSort(v2, &greaterThan); printList(v2, FLT_SZ, FLT_LN); v2.clear(); cout << “nSecond list – ascending order:nn”; buildList(v2, D2); mergeSort(v2, &lessThan); printList(v2, FLT_SZ, FLT_LN); // Sort and print third list cout << left; cout << “nThird list – ascending order:nn”; buildList(v3, D3); quickSort(v3, &lessThan); printList(v3, STR_SZ, STR_LN); v3.clear(); cout << “nThird list – descending order:nn”; buildList(v3, D3); mergeSort(v3, &greaterThan); printList(v3, STR_SZ, STR_LN); // print termination message cout << “n*** End of program execution ***n”; return 0; }

Expert Answer

---

Answer to For this final part of the assignment you will write several C++ template functions to sort a list of items using the re… . . .