In C$++$ Please dont copy other solutions.

The purpose of the programming assignment is to perform empirical comparative

analysis of several modifications of Quicksort for integer arrays.

A$.[80$ points$]$ Implement the following:

basic version of Quicksort as discussed in our textbook;

Quicksort with switching to Insertion sort when the number of elements in the subarray is

less than or equal to $2\%$ of the original number;

Quicksort with 'median$-$of$-$three' partitioning;

Quicksort with randomly selected pivot value.

Requirements:

functions from standard libraries implementing Quicksort are NOT allowed;

however, you can use any code from any other sources with proper references;

for obtaining the working time of each algorithm for a particular array, use the

same function as for part $($C$)$ of Project #$1$; call this function before and after a call

to the function implementing a sorting algorithm;

run your functions for the following types of arrays containing $1000,10000$ and

$100000$ integers: random numbers, sorted list, almost sorted list, in which every

$10^("$th $")$ number is out of order $($random number$)$;

the size of integers is supposed to be from $1$ to $10000$ ;

submit: $(1)$ source code with the results; $(2)$ the analysis of your experiments;

please, do NOT include original and sorted arrays in your output!

your source code MUST include information on the name of the programmer and

the purpose of the project, as well as some other comments.

B$.[20$ points$]$ Analysis of the experiments.

Requirements to the analysis:

the text must be TYPED;

your analysis must include theoretical information about the efficiency of Quicksort and

how it may be improved using all approaches suggested in this project;

experimental results must be clearly presented in the form of the table and graphs;

I expect to see your conclusions on how well the experimental results correspond to the

theory, and which version of Quicksort works better for specific types of input.