Recursive RANDOMIZED *Quick Sort*

1. The code below uses the first element of the array as a pivot. EDIT the code so that the pivot is chosen at RANDOM.

2. Run the code and show screenshot showing that it works.

//--------------------------------------------------------------------------

#include using namespace std;

//5, 2, 6, 1, 3, 4

void swap(double &x, double &y) {

double t = x;

x = y;

y = t;

}

int partition (double * arr, int start, int end) { int pivot = arr[start]; // pivot

int i = end; for (int j = end-1; j >= start+1; j--) { // If current element is greater than or // equal to pivot if (arr[j] >= pivot) { i--; // decrement index of greater element swap(arr[i], arr[j]); } }

swap(arr[i - 1], arr[start]); return i; }

void quickSort(double * arr, int start, int end) { if ((end-start) < 1) { //do nothing } else { int pi = partition(arr, start, end); quickSort(arr, start, pi - 1); quickSort(arr, pi + 1, end); } }

int main() { double arr[] = {5, 2, 6, 1, 3, 4}; quickSort(arr, 0, 6); for (int i = 0; i < 6; i++) { cout << arr[i] << endl; }

return 0;

}