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;