// Code in C++ // This is the base of the quicksort app, with the pivoting code provided. // Your job is to fill in the missing functions (quicksort, printArray, and swap) // to make quicksort work #include  using namespace std; void quicksort(int array[], int start, int end); int doPivot(int array[], int start, int end); void printArray(int array[], int firstIndex, int lastIndex); void swap(int array[], int firstIndex, int secondIndex); int main() { int array[] = { 40, 50, 27, 62, 53, 53, 71, 99, 33, 24, 59, 14, 34, 32, 79, 13, 6, 8, 84, 79, 24, 92, 75, 14, 1, 18, 25, 75, 63, 37, 13, 14, 15, 10, 61, 2, 21, 16, 76, 24, 88, 74, 55, 58, 72, 12, 78, 72, 57, 83 }; int length = sizeof(array) / 4; quicksort(array, 0, length - 1); printArray(array, 0, length - 1); } void quicksort(int array[], int start, int end) { // TODO: This is the recursive function. You need to check for the base case // as well as do the recursion. doPivot will tell you where the middle is; // you then need to apply quicksort to the left and right sides of the middle cout << "Quicksort from " << start << " to " << end << endl; } int doPivot(int array[], int start, int end) { int middle = (start + end) / 2; cout << "Pivoting around " << middle << " (" << array[middle] << ")" << endl; int pivotValue = array[middle]; // Move the middle value to the end swap(array, middle, end); int firstIndexGreaterThanPivotValue = end; // To make things easier, find the first value > the pivot and swap that to the end - 1 for (int i = end - 1; i >= 0; i--) { if (array[i] > pivotValue) { swap(array, i, end - 1); firstIndexGreaterThanPivotValue = end - 1; break; } } if (firstIndexGreaterThanPivotValue == end) { // Bad pivot; everything is less than it return end; } // Now shift all values > middle to the right // Start with end - 2 because we know end - 1 is > the pivot for (int i = end - 2; i >= 0; i--) { if (array[i] > pivotValue) { firstIndexGreaterThanPivotValue--; // Needs to go to the right swap(array, i, firstIndexGreaterThanPivotValue); } } // Now put the pivot in the right place swap(array, firstIndexGreaterThanPivotValue, end); printArray(array, start, end); return firstIndexGreaterThanPivotValue; } void printArray(int array[], int start, int end) { // TODO: Fill in (print the array neatly) } void swap(int array[], int firstIndex, int secondIndex) { // TODO: Fill in (swap the values) }