#include

using namespace std;

int partition$($int arr$[],$ int left, int right$)\{$

int pivot $=\_\_\_$; $//$Task $3$: consider the last element of the array as a pivot

int pIndex $=$ left; $//$pIndex represents the actual index of the pivot in the sorted list

$//$set pIndex to the left index initailly

for$($int i $=$ left; i $<\_\_\_$; i$++)\{//$Task $4$

if $(\_\_\_<=\_\_\_)\{//$Task $5$

swap$(\_\_\_,\_\_\_)$; $//$Task $6$: swap when an element $<=$ pivot

pIndex $=\_\_\_$; $//$Task $7$

$\}$

$\}$

swap$($arr$[$pIndex$],$ arr$[$right$])$; $//$swap arr$[$end$],$ i$.$e$.,$ the pivot, with the element at pIndex

$//$ The previous line helps to place the pivot in its proper place in the sorted array

return $\_\_\_$; $//$Task $8$

$\}$

void quick$\_$sort$($int arr$[],$ int left, int right$)\{$

if$($left $<$ right$)\{$

int pIndex $=$ partition$($arr$,$ left, right$)$;

quick$\_$sort$($arr$,\_\_\_,\_\_\_)$; $//$Task $1$: recursively call the function for the left subarray of the pivot

quick$\_$sort$($arr$,\_\_\_,\_\_\_)$; $//$Task $2$: recursively call the function for the right subarray of the pivot

$\}$

$\}$

$//$ Print the array

void printArray$($int arr$[],$ int size$)\{$

for $($int i $=0$; i $<$ size; i$++)$

cout $<<$ arr$[$i$]<<""$;

cout $<<$ endl;

$\}$

$//$ Driver program

int main$()\{$

int arr$[]=\{16,55,12,-23,94,11,45,2,-64,7\}$;

int size $=$ sizeof$($arr$)/$ sizeof$($arr$[0])$;

cout $<<$ "Unsorted array: $"$;

printArray$($arr$,$ size$)$;

quick$\_$sort$($arr$,0,$ size $-1)$;

cout $<<$ "Sorted array: $"$;

printArray$($arr$,$ size$)$;

return $0$;

$\}$ In this assignment, your task is to modify the existing Quick Sort code to randomly choose the pivot element, which can help improve the algorithm's performance in avoiding worst$-$case scenarios.

Tasks:

Modify the partition function to include a step that randomly selects a pivot index within the subarray range. You can use the rand$()$ function along with proper indexing to achieve this.

Implement the randomized pivot selection in the partition function by swapping the randomly chosen pivot element with the last element of the subarray.