Quicksort function help. All other functions written, only write the quickSort() function.

#include "QuickSort.hpp"

#include #include #include #include using namespace std;

class quicksort { private: int left; int right; int* array; public: void swapListValues(int* array, int left, int right ); int findAndSwapPivot(int* array, int left, int right ); int partitionList(int* array, int left, int right, int pivot ); void quickSort(int* array, int left, int right ); };

void quicksort::swapListValues(int* array, int left, int right ) { int temp = array[left]; array[left] = array[right]; array[right] = temp; }

int quicksort::findAndSwapPivot(int* array, int left, int right ) { int temp = (right + left) / 2; int pivot = array[temp];

swapListValues(array, temp, right );

return pivot; }

int quicksort::partitionList(int* array, int left, int right, int pivot)

{

// one lower than range int smallerIndex = left-1; // start at rightmost element int largerIndex = right + 1;

//infinite loop while conditions are met for (;;) { // find a larger-than-pivot element starting from the left while (array[++smallerIndex]

while (pivot

if (smallerIndex >= largerIndex) break; swapListValues(array, smallerIndex, largerIndex); }

// return the index of the pivot-position return smallerIndex; }

Function to write

void quicksort::quickSort(int* array, int left, int right) { }

Main function to test code.

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; quicksort sortAndSearch;

// sort a list of size 2, not in order length = 2; memcpy(testvals, (const int[]){9, 3}, sizeof(int) * length); memcpy(expected, (const int[]){3, 9}, sizeof(int) * length); sortAndSearch.quickSort(testvals, 0, length-1); cout

// sort an odd sized list length = 9; memcpy(testvals, (const int[]){9, 3, 2, 7, 5, 8, 6, 5, 4}, sizeof(int) * length); memcpy(expected, (const int[]){2, 3, 4, 5, 5, 6, 7, 8, 9}, sizeof(int) * length); sortAndSearch.quickSort(testvals, 0, length-1); cout

return 0;

}

Conceptually the steps of the Quicksort algorithm are as follows: l. if list size is 0 or l (left -to the pivot value is at indicates the new left and right side sub-lists 4. Swap the pivot value to its correct position k swap(k, right) 5. Recursively call Quicksort on the new left and right sub-lists quicksort (A, left, k-1) quicksort(A, k+1, right)