For this part of the assignment you will write a pair of C++ template functions to read a series of items from an input file, and then print the items.

Program

Implement the following template functions in a header file called sorts.h. This header file should have header guards (as usual) and should contain both the prototypes and definitions for the functions.

template void buildList(vector& set, const char* fileName)

This function should read items from an input file and put them into a vector. The first argument to this function is a reference to a vector object that will be used to store the items. The second argument is a C-style string containing the full pathname of the input file.

The function should first open the file for input, then read items from the file using the >> operator one at a time until end of file, inserting them into the vector. Finally, it should close the input file. Here's some pseudocode for the logic:

T item; ifstream inFile;

Open inFile for input using fileName as the name of the file to open Check that the file has been successfully opened

Read item from input file while (not end of file) { set.push_back(item); Read item from input file }

Close the input file template void printList(const vector& set, int itemWidth, int numPerLine)

This function should print a list of items stored in a vector. The first argument to this function is a reference to a constant vector object that will contain the items to print. The second argument is an integer specifying the width an individual item should occupy when printed. The third argument is an integer specifying the maximum number of items that should be printed in a single line of output.

A driver program, assign8.cpp, is provided below to test your code for this part of the assignment. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2017/Assign8/Part1/assign8.cpp.

/********************************************************************* PROGRAM: CSCI 241 Assignment 8, Part 1 PROGRAMMER: your name LOGON ID: your z-ID DUE DATE: due date of assignment FUNCTION: This program builds and sorts lists using the quick sort algorithm. *********************************************************************/

#include #include #include #include #include "sorts.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/Spring2017/Assign8/data8a.txt" #define D2 "/home/turing/t90kjm1/CS241/Data/Spring2017/Assign8/data8b.txt" #define D3 "/home/turing/t90kjm1/CS241/Data/Spring2017/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 line

int main() { vector v1; // vector of integers vector v2; // vector of floating-pt nums vector v3; // vector of strings

// Print header message cout << "*** CSCI 241: Assignment 8 - Part 1 Output *** ";

// Build and print first list

cout << "First list: "; buildList(v1, D1); printList(v1, INT_SZ, INT_LN);

// Build and print second list

cout << fixed << setprecision(2);

cout << " Second list: "; buildList(v2, D2); printList(v2, FLT_SZ, FLT_LN);

// Build and print third list

cout << left;

cout << " Third list: "; buildList(v3, D3); printList(v3, STR_SZ, STR_LN);

// Print termination message cout << " *** End of program execution *** ";

return 0; } The STL Vector Class

The vector class is part of the C++ Standard Template Library. It is a template class that provides an alternative to using an array.

The vector class is implemented as a dynamic array. Just like a regular array, a vector has its elements stored in contiguous storage locations. But unlike regular arrays, storage in a vector is handled automatically, allowing it to be expanded and contracted as needed.

Vectors are good at:

Accessing individual elements by their position index. Iterating over the elements in any order. Adding to and removing elements from the tail end of the vector. Compared to arrays, they provide almost the same performance for these tasks, plus they have the ability to be easily resized. They usually consume more memory than arrays when their capacity is handled automatically (this is in order to accommodate extra storage space for future growth).

Example Vector Operations

To create an empty vector, you can use the default constructor:

vector v1; // Create an empty vector of integers You can also create a vector of a specific initial size:

vector v1(20); // Create a vector of integers with size 20 To add a new element to the tail end of a vector, you can use the push_back() method:

v1.push_back(12); // Add a new element with value 12 to the tail end of the vector You can use a for loop and the subscript operator to loop through the elements of a vector, similar to the way you would loop through an array:

for (int i = 0; i < (int) v1.size(); i++) cout << v1[i] << ' ';

cout << endl; (The size() method typically returns an unsigned int, so we need to perform a type cast to avoid a warning from the compiler.)

Vectors also have an at() method that will throw an out_of_range exception if you try to access an element outside the bounds of the dynamic array.

For this part of the assignment you will write a number of C++ template functions to sort a list of items using the recursive quick sort algorithm.

Program

Add the following template functions to your sorts.h file. The header file should contain both the prototypes and definitions for these functions.

template bool lessThan(const T& item1, const T& item2)

This function should return true if item1 is less than item2 and false if not. You may assume that the data type T can be compared using the standard relational operators.

template bool greaterThan(const T& item1, const T& item2)

This function should return true if item1 is greater than item2 and false if not. You may assume that the data type T can be compared using the standard relational operators.

Implement the following template functions in a header file called quicksort.h. This header file should have header guards (as usual) and should contain both the prototypes and definitions for the functions.

template void quickSort(vector& set, bool (*compare)(const T&, const T&))

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

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

quickSort(set, 0, set.size()-1, compare); template void quickSort(vector& set, int start, int end, bool (*compare)(const T&, const T&))

This function performs the recursive calls to implement the quick sort algorithm. The logic is:

int pivotPoint;

if (start < end) { pivotPoint = partition(set, start, end, compare); // Get the pivot point quickSort(set, start, pivotPoint - 1, compare); // Sort first sublist quickSort(set, pivotPoint + 1, end, compare); // Sort second sublist } template int partition(vector& set, int start, int end, bool (*compare)(const T&, const T&))

This function selects a pivot element and then partitions the vector around the pivot. The logic is:

int pivotIndex, mid; T pivotValue; mid = (start + end) / 2;

Swap elements start and mid of the vector pivotIndex = start; pivotValue = set[start]; for (int scan = start + 1; scan <= end; scan++) { if (compare(set[scan], pivotValue)) { pivotIndex++; Swap elements pivotIndex and scan of the vector } }

Swap elements start and pivotIndex of the vector

return pivotIndex; A driver program, assign8.cpp, is provided below to test your code for this part of the assignment. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2017/Assign8/Part2/assign8.cpp.

/********************************************************************* PROGRAM: CSCI 241 Assignment 8, Part 2 PROGRAMMER: your name LOGON ID: your z-ID DUE DATE: due date of assignment FUNCTION: This program builds and sorts lists using the quick sort algorithm. *********************************************************************/

#include #include #include #include #include "sorts.h" #include "quicksort.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/Spring2017/Assign8/data8a.txt" #define D2 "/home/turing/t90kjm1/CS241/Data/Spring2017/Assign8/data8b.txt" #define D3 "/home/turing/t90kjm1/CS241/Data/Spring2017/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 line

int main() { vector v1; // vector of integers vector v2; // vector of floating-pt nums vector v3; // vector of strings

// Print header message cout << "*** CSCI 241: Assignment 8 - Part 2 Output *** ";

// sort and print first list

cout << "First list - ascending order: "; buildList(v1, D1); quickSort(v1, &lessThan); printList(v1, INT_SZ, INT_LN);

// Sort and print second list

cout << fixed << setprecision(2);

cout << " Second list - descending order: "; buildList(v2, D2); quickSort(v2, &greaterThan); printList(v2, FLT_SZ, FLT_LN);

// Sort and print third list

cout << left;

cout << " Third list - ascending order: "; buildList(v3, D3); quickSort(v3, &lessThan); printList(v3, STR_SZ, STR_LN);

// print termination message cout << " *** End of program execution *** ";

return 0; }

Implement the following template functions in a header file called mergesort.h. This header file should have header guards (as usual) and should contain both the prototypes and definitions for the functions.

template void mergeSort(vector& set, bool (*compare)(const T&, const T&))

This function should sort the items in the vector set using the merge sort algorithm. The first argument to this function is a reference to a vector object containing the list of items to sort. The second argument is a pointer to a comparison function that can be 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 is set.size() - 1), and the pointer to the comparison function (compare), e.g.:

mergeSort(set, 0, set.size()-1, compare); template void mergeSort(vector& set, int low, int high, 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 (low < high) { mid = (low + high) / 2; // Divide and conquer mergeSort(set, low, mid, compare); mergeSort(set, mid+1, high, compare); // Combine merge(set, low, mid, high, compare); } } template void merge(vector& set, int low, int mid, int high, bool (*compare)(const T&, const T&))

This function merges two sorted subvectors.

// Create temporary vector to hold merged subvectors vector temp(high - low + 1);

int i = low; // 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 <= high) { if (compare(set[j], set[i])) { Copy element j of set into element k of temp Add one to j Add one to k } else { Copy element i of set into element k of temp Add one to i 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 <= high) { 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 = low; j <= high; i++, j++) Copy element i of temp into element j of set A driver program, assign8.cpp, is provided below to test your code for this part of the assignment. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2017/Assign8/Part3/assign8.cpp.

/********************************************************************* PROGRAM: CSCI 241 Assignment 8 PROGRAMMER: your name LOGON ID: your z-ID DUE DATE: due date of assignment FUNCTION: This program builds and sorts lists using the quick sort algorithm. *********************************************************************/

#include #include #include #include #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/Spring2017/Assign8/data8a.txt" #define D2 "/home/turing/t90kjm1/CS241/Data/Spring2017/Assign8/data8b.txt" #define D3 "/home/turing/t90kjm1/CS241/Data/Spring2017/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 line

int main() { vector v1; // vector of integers vector v2; // vector of floating-pt nums vector v3; // vector of strings

// Print header message cout << "*** CSCI 241: Assignment 8 - Output *** ";

// sort and print first list

cout << "First list - ascending order: "; buildList(v1, D1); quickSort(v1, &lessThan); printList(v1, INT_SZ, INT_LN);

v1.clear();

cout << " First list - descending order: "; buildList(v1, D1); mergeSort(v1, &greaterThan); printList(v1, INT_SZ, INT_LN);

// Sort and print second list

cout << fixed << setprecision(2);

cout << " Second list - descending order: "; buildList(v2, D2); quickSort(v2, &greaterThan); printList(v2, FLT_SZ, FLT_LN);

v2.clear();

cout << " Second list - ascending order: "; buildList(v2, D2); mergeSort(v2, &lessThan); printList(v2, FLT_SZ, FLT_LN);

// Sort and print third list

cout << left;

cout << " Third list - ascending order: "; buildList(v3, D3); quickSort(v3, &lessThan); printList(v3, STR_SZ, STR_LN);

v3.clear();

cout << " Third list - descending order: "; buildList(v3, D3); mergeSort(v3, &greaterThan); printList(v3, STR_SZ, STR_LN);

// print termination message cout << " *** End of program execution *** ";

return 0; }

Data8a.txt:_____________________

28 -647 -382 69 895 -655 404 -546 -9 -749 -831 -220 -444 -263 966 71 531 293 534 560 646 -695 251 -369 -305 834 40 -197 213 571 863 739 733 349 517 164 -220 -288 -598 654 -167 -72 958 -746 -573 916 475 -181 560 516 913 -942 -361 514 -513 179 -912 912 -361 -880 -115 830 144 -761 139 -495 -7 -525 -45 -187 746 -145 -282 -235 -912 -677 45 393 -804 -197 547 -509 -313 -539 -403 -390 774 -925 302 -202 352 465 875 -532 677 934 557 -136 348 618

Data8b.txt___________________________________ -126.17 -329.04 -170.40 163.42 -279.66 355.67 -207.22 59.06 184.38 189.87 454.23 -834.74 64.03 -630.81 -191.03 -251.65 398.76 -1.87 468.44 378.53 -280.54 580.12 350.48 299.95 -441.58 387.50 -290.67 0.63 -680.65 -728.50 565.64 -497.48 -492.66 132.27 -323.52 -688.54 -361.08 -391.15 -254.70 -152.79 711.98 -330.79 -648.02 113.42 455.87 580.20 -397.21 167.67 -18.69 337.60 -239.58 -208.58 -209.56 -583.92 -286.04 200.05 346.79 199.22 168.89 -327.15 365.32 -430.49 177.14 -176.99 42.38 118.35 -393.01 87.63 105.74 76.02 -286.83 197.70 104.55 721.75 -473.20 -391.86 499.40 873.65 225.40 -32.23 -567.73 878.72 2.91 -10.69 136.53 -237.10 -40.34 -180.62 486.99 -778.98 -267.60 88.52 29.85 6.82 344.29 201.17 -587.31 -157.06 974.89 425.67

data8c.txt___________________ PREFACE This is a book about the computer language called C If you are seeking a book to increase your typing speed expand on your knowledge of word processing or learn the secrets of chip fabrication and design this is not the one for you However if you want to become thoroughly familiar with the C programming language then you have made a wise choice For this book is devoted to just that help you become proficient in C It is one thing to read about a language it is quite another to get involved in it The best and

Part 1 output:_________________________________

First list:

28 -647 -382 69 895 -655 404 -546 -9 -749 -831 -220 -444 -263 966 71 531 293 534 560 646 -695 251 -369 -305 834 40 -197 213 571 863 739 733 349 517 164 -220 -288 -598 654 -167 -72 958 -746 -573 916 475 -181 560 516 913 -942 -361 514 -513 179 -912 912 -361 -880 -115 830 144 -761 139 -495 -7 -525 -45 -187 746 -145 -282 -235 -912 -677 45 393 -804 -197 547 -509 -313 -539 -403 -390 774 -925 302 -202 352 465 875 -532 677 934 557 -136 348 618

Second list:

-126.17 -329.04 -170.40 163.42 -279.66 355.67 -207.22 59.06 184.38 189.87 454.23 -834.74 64.03 -630.81 -191.03 -251.65 398.76 -1.87 468.44 378.53 -280.54 580.12 350.48 299.95 -441.58 387.50 -290.67 0.63 -680.65 -728.50 565.64 -497.48 -492.66 132.27 -323.52 -688.54 -361.08 -391.15 -254.70 -152.79 711.98 -330.79 -648.02 113.42 455.87 580.20 -397.21 167.67 -18.69 337.60 -239.58 -208.58 -209.56 -583.92 -286.04 200.05 346.79 199.22 168.89 -327.15 365.32 -430.49 177.14 -176.99 42.38 118.35 -393.01 87.63 105.74 76.02 -286.83 197.70 104.55 721.75 -473.20 -391.86 499.40 873.65 225.40 -32.23 -567.73 878.72 2.91 -10.69 136.53 -237.10 -40.34 -180.62 486.99 -778.98 -267.60 88.52 29.85 6.82 344.29 201.17 -587.31 -157.06 974.89 425.67

Third list:

PREFACE This is a book about the computer language called C If you are seeking a book to increase your typing speed expand on your knowledge of word processing or learn the secrets of chip fabrication and design this is not the one for you However if you want to become thoroughly familiar with the C programming language then you have made a wise choice For this book is devoted to just that help you become proficient in C It is one thing to read about a language it is quite another to get involved in it The best and

*** End of program execution ***

Part 2 output__________________________ First list - ascending order:

-942 -925 -912 -912 -880 -831 -804 -761 -749 -746 -695 -677 -655 -647 -598 -573 -546 -539 -532 -525 -513 -509 -495 -444 -403 -390 -382 -369 -361 -361 -313 -305 -288 -282 -263 -235 -220 -220 -202 -197 -197 -187 -181 -167 -145 -136 -115 -72 -45 -9 -7 28 40 45 69 71 139 144 164 179 213 251 293 302 348 349 352 393 404 465 475 514 516 517 531 534 547 557 560 560 571 618 646 654 677 733 739 746 774 830 834 863 875 895 912 913 916 934 958 966

Second list - descending order:

974.89 878.72 873.65 721.75 711.98 580.20 580.12 565.64 499.40 486.99 468.44 455.87 454.23 425.67 398.76 387.50 378.53 365.32 355.67 350.48 346.79 344.29 337.60 299.95 225.40 201.17 200.05 199.22 197.70 189.87 184.38 177.14 168.89 167.67 163.42 136.53 132.27 118.35 113.42 105.74 104.55 88.52 87.63 76.02 64.03 59.06 42.38 29.85 6.82 2.91 0.63 -1.87 -10.69 -18.69 -32.23 -40.34 -126.17 -152.79 -157.06 -170.40 -176.99 -180.62 -191.03 -207.22 -208.58 -209.56 -237.10 -239.58 -251.65 -254.70 -267.60 -279.66 -280.54 -286.04 -286.83 -290.67 -323.52 -327.15 -329.04 -330.79 -361.08 -391.15 -391.86 -393.01 -397.21 -430.49 -441.58 -473.20 -492.66 -497.48 -567.73 -583.92 -587.31 -630.81 -648.02 -680.65 -688.54 -728.50 -778.98 -834.74

Third list - ascending order:

C C C For However If It PREFACE The This a a a a about about and and another are become become best book book book called chip choice computer design devoted expand fabrication familiar for get have help if in in increase involved is is is is is it it just knowledge language language language learn made not of of on one one or processing proficient programming quite read secrets seeking speed that the the the the then thing this this thoroughly to to to to to typing want wise with word you you you you you your your

*** End of program execution ***

Part 3 and final output_________________________

First list - ascending order:

-942 -925 -912 -912 -880 -831 -804 -761 -749 -746 -695 -677 -655 -647 -598 -573 -546 -539 -532 -525 -513 -509 -495 -444 -403 -390 -382 -369 -361 -361 -313 -305 -288 -282 -263 -235 -220 -220 -202 -197 -197 -187 -181 -167 -145 -136 -115 -72 -45 -9 -7 28 40 45 69 71 139 144 164 179 213 251 293 302 348 349 352 393 404 465 475 514 516 517 531 534 547 557 560 560 571 618 646 654 677 733 739 746 774 830 834 863 875 895 912 913 916 934 958 966

First list - descending order:

966 958 934 916 913 912 895 875 863 834 830 774 746 739 733 677 654 646 618 571 560 560 557 547 534 531 517 516 514 475 465 404 393 352 349 348 302 293 251 213 179 164 144 139 71 69 45 40 28 -7 -9 -45 -72 -115 -136 -145 -167 -181 -187 -197 -197 -202 -220 -220 -235 -263 -282 -288 -305 -313 -361 -361 -369 -382 -390 -403 -444 -495 -509 -513 -525 -532 -539 -546 -573 -598 -647 -655 -677 -695 -746 -749 -761 -804 -831 -880 -912 -912 -925 -942

Second list - descending order:

974.89 878.72 873.65 721.75 711.98 580.20 580.12 565.64 499.40 486.99 468.44 455.87 454.23 425.67 398.76 387.50 378.53 365.32 355.67 350.48 346.79 344.29 337.60 299.95 225.40 201.17 200.05 199.22 197.70 189.87 184.38 177.14 168.89 167.67 163.42 136.53 132.27 118.35 113.42 105.74 104.55 88.52 87.63 76.02 64.03 59.06 42.38 29.85 6.82 2.91 0.63 -1.87 -10.69 -18.69 -32.23 -40.34 -126.17 -152.79 -157.06 -170.40 -176.99 -180.62 -191.03 -207.22 -208.58 -209.56 -237.10 -239.58 -251.65 -254.70 -267.60 -279.66 -280.54 -286.04 -286.83 -290.67 -323.52 -327.15 -329.04 -330.79 -361.08 -391.15 -391.86 -393.01 -397.21 -430.49 -441.58 -473.20 -492.66 -497.48 -567.73 -583.92 -587.31 -630.81 -648.02 -680.65 -688.54 -728.50 -778.98 -834.74

Second list - ascending order:

-834.74 -778.98 -728.50 -688.54 -680.65 -648.02 -630.81 -587.31 -583.92 -567.73 -497.48 -492.66 -473.20 -441.58 -430.49 -397.21 -393.01 -391.86 -391.15 -361.08 -330.79 -329.04 -327.15 -323.52 -290.67 -286.83 -286.04 -280.54 -279.66 -267.60 -254.70 -251.65 -239.58 -237.10 -209.56 -208.58 -207.22 -191.03 -180.62 -176.99 -170.40 -157.06 -152.79 -126.17 -40.34 -32.23 -18.69 -10.69 -1.87 0.63 2.91 6.82 29.85 42.38 59.06 64.03 76.02 87.63 88.52 104.55 105.74 113.42 118.35 132.27 136.53 163.42 167.67 168.89 177.14 184.38 189.87 197.70 199.22 200.05 201.17 225.40 299.95 337.60 344.29 346.79 350.48 355.67 365.32 378.53 387.50 398.76 425.67 454.23 455.87 468.44 486.99 499.40 565.64 580.12 580.20 711.98 721.75 873.65 878.72 974.89

Third list - ascending order:

C C C For However If It PREFACE The This a a a a about about and and another are become become best book book book called chip choice computer design devoted expand fabrication familiar for get have help if in in increase involved is is is is is it it just knowledge language language language learn made not of of on one one or processing proficient programming quite read secrets seeking speed that the the the the then thing this this thoroughly to to to to to typing want wise with word you you you you you your your

Third list - descending order:

your your you you you you you word with wise want typing to to to to to thoroughly this this thing then the the the the that speed seeking secrets read quite programming proficient processing or one one on of of not made learn language language language knowledge just it it is is is is is involved increase in in if help have get for familiar fabrication expand devoted design computer choice chip called book book book best become become are another and and about about a a a a This The PREFACE It If However For C C C

*** End of program execution ***