C++Write a function called swapListValues(). This functions takes an array of integers as its rst parameter, and two indexes (the left and right indexes). This function does not return a value explicitly. Recall arrays are passed by reference. As the name implies, the two values in the array at the indicated left and right indexes are to be swapped, and since the array is passed by reference, after returning they will be swapped for the caller of this function.

2. Write a function called findAndSwapPivot(). This function takes the same 3 parameters, an array of integers, and two indexes indicating the left and right sides of a sub-portion of the list. The function should nd the value in the middle of the left and right ends, which will be chosen as the pivot. The function should use the previous swapListValues() function to swap the chosen pivot value to the end of the list of integers. This function returns a value. This is dierent from how the textbook implements the nd pivot function. Our function should return the actual pivot value that was chosen (not the pivotIndex, which we know should be the last index of the sub-list after calling this function).

3. Write a function called partitionList(). This will implement the algorithm described preciously. This functions takes the 3 same parameters for the previous functions, an integer array, and left and right indexes for the sub-portion of the list we are currently partitioning. In addition, this function takes a fourth parameter, the pivot value). This function should make use of the swapListValues() function de- ned previously when swapping values in-place in the list of integers. When this function is called, the pivot has been swapped to the end of the sub-portion of the list, so the right index will be one less than this. This function needs to correctly return the index, described as k above, where the pivot value should actually go. At the end, the location where the left search and right search meet will be this index, the nal location found for the pivot value.

4. Finally write a function called quickSort() using the described algorithm above. This function will use all of the 3 previous functions to do its work. If implemented correctly, there is almost nothing to be done in this function besides calling the other 3 functions, and recursively calling itself (except to check for the base case of your recursion).

Examples on what it has to sort

#include #include #include #include #include "QuickSort.hpp" using namespace std;

/** list to string * Represent array as a string time, useful for output. * * @param list[] The list, an array of integers, to be converted to * a string. * @param length The length of the list. * * @returns string Returns a string with a representation of the list * state and it contents. */ string tostring(int list[], int length) { ostringstream out;

out << "List length: " << length << " ["; // output first value, so we can remove , at end if (length >= 1) { out << list[0]; }

// output each follow with a preceeding comma, // which allows us to end list without trailing , for (int index = 1; index < length; index++) { out << ", " << list[index]; } out << "]"; return out.str(); }

/** compare lists equal * This function compares if the two lists (arrays of integers) * given as parameters are equal or not. Result is boolean true * if lists all have the same values, false otherwise. * * @param a[], b[] The lists, both of int and both the same size, * that are to be compared. * @param length The length of both of the lists. * * @returns bool Returns true if the lists are equal (have all the * same values at all the same positions) and false otherwise. */ bool listsAreEqual(int a[], int b[], int length) { // compare each item in a and b for (int index = 0; index < length; index++) { // as soon as we find 1 value that differs, the answer is false, // the lists are not equal if (a[index] != b[index]) { return false; } }

// at this point we compared every value and they were all the // same, thus the lists must be equal return true; }

/** main * The main entry point for this program. Execution of this program * will begin with this main function. * * @param argc The command line argument count which is the number of * command line arguments provided by user when they started * the program. * @param argv The command line arguments, an array of character * arrays. * * @returns An int value indicating program exit status. Usually 0 * is returned to indicate normal exit and a non-zero value * is returned to indicate an error condition. */ int main(int argc, char** argv) { // variables used for the function/unit tests const int MAX_TEST_SIZE = 100; int testvals[MAX_TEST_SIZE]; int expected[MAX_TEST_SIZE]; int length; // test of swap function ------------------------------------------------ cout << "Test swapListValues() ------------------------------------------" << endl; // basic test length = 2; memcpy(testvals, (const int[]){5, 10}, sizeof(int) * length); memcpy(expected, (const int[]){10, 5}, sizeof(int) * length); // swapListValues(testvals, 0, 1); // cout << "swapListValues() test 1, swap 2 values" << endl // << " expected: " << tostring(expected, length) << endl // << " actual : " << tostring(testvals, length) << endl // << endl; // assert(listsAreEqual(testvals, expected, length));

// test if indexes are equal, important, should not cause any change length= 2; memcpy(testvals, (const int[]){8, 6}, sizeof(int) * length); memcpy(expected, (const int[]){8, 6}, sizeof(int) * length); // swapListValues(testvals, 1, 1); // cout << "swapListValues() test 2, same index" << endl // << " expected: " << tostring(expected, length) << endl // << " actual : " << tostring(testvals, length) << endl // << endl; // assert(listsAreEqual(testvals, expected, length));

// more general tests, swap values in middle of list length = 12; memcpy(testvals, (const int[]){2, 7, 9, 3, 8, 4, 2, 9, 5, 8, 6, 1}, sizeof(int) * length); memcpy(expected, (const int[]){2, 7, 6, 3, 8, 4, 2, 9, 5, 8, 9, 1}, sizeof(int) * length); // swapListValues(testvals, 2, 10); // cout << "swapListValues() test 3, swap 2 values from inside of list" << endl // << " expected: " << tostring(expected, length) << endl // << " actual : " << tostring(testvals, length) << endl // << endl; // assert(listsAreEqual(testvals, expected, length));

// swap back, reverse indexes in function call // continuing to use testvals after previous test here length = 12; memcpy(expected, (const int[]){2, 7, 9, 3, 8, 4, 2, 9, 5, 8, 6, 1}, sizeof(int) * length); // swapListValues(testvals, 10, 2); // cout << "swapListValues() test 4, reverse the previous swap" << endl // << " expected: " << tostring(expected, length) << endl // << " actual : " << tostring(testvals, length) << endl // << endl; // assert(listsAreEqual(testvals, expected, length));

// swap with index 0 on a bigger list // still using previous testvals length = 12; memcpy(expected, (const int[]){4, 7, 9, 3, 8, 2, 2, 9, 5, 8, 6, 1}, sizeof(int) * length); // swapListValues(testvals, 5, 0); // cout << "swapListValues() test 5, swap with index 0" << endl // << " expected: " << tostring(expected, length) << endl // << " actual : " << tostring(testvals, length) << endl // << endl; // assert(listsAreEqual(testvals, expected, length));