Quicksort method:

int left;

int right;

const inst SIZE = 10;

int A[size];

Then to sort the whole list we set left = 0 and right = 9 to initially call the Quicksort function:

left = 0;

right = size-1;

quicksort(A, left, right);

Conceptually the steps of the Quicksort algorithm are as follows: 1. if list si

ze is 0 or 1 (left <= right) return(lists of size are sorted by definition)

2. Choose a pivot and swap the pivot value to the end of the list swap(pivotindex, right)

3. partition the list.

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)

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 defined 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 final 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).

Given functions:

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

int findAndSwapPivot(int* array, int left, int right) { int temp = (right + left) / 2; int pivot = array[temp]; swapListValues(array, temp, right); return pivot; }

must be able to run on these test:

length = 15; int testvals12[] = { 12, 7, 10, 19, 6, 18, 12, 15, 6, 10, 4, 13, 11, 17, 10 }; int expected12[] = { 4, 7, 6, 6, 19, 18, 12, 15, 10, 10, 12, 13, 11, 17, 10 }; expectedPivotIndex = 4; actualPivotIndex = partitionList(testvals12, 0, length-2, testvals12[length-1]); cout << "partitionList() test 2, bigger test and some duplicates of the pivot" << endl << " expected: " << tostring(expected12, length) << endl << " expected pivot: " << expectedPivotIndex <

length = 9; int testvals22[] = { 9, 3, 2, 7, 5, 8, 6, 5, 4 }; int expected22[] = { 2, 3, 4, 5, 5, 6, 7, 8, 9 }; quickSort(testvals22, 0, length-1); cout << "quickSort() test 4, sort odd sized list" << endl << " expected: " << tostring(expected22, length) << endl << " actual: " << tostring(testvals22, length) << endl << endl; assert(listsAreEqual(testvals22, expected22, length));