THIS IS PROJECT IS LONGER SO PLEASE EMAIL ME AT XXSTUPIDMEXICAN@AOL.COM FOR THE REST OF IT$,$ iWILL PAY IF NEEDED.

The input consists of two parts:

$-$ The first line is the header, which is text describing the data.

$-$ The second line is the data itself, which consists of integers separated by spaces.

Test input $1$ has $1$K integers, test input $2$ has $100$K$,$ test input $3$ has $10$M$.$

For this project, given an input file of integer values, you will compute all the statistics included in a five$-$number summary or a box plot: the minimum value, the $25$th$,50$th$,$ and $75$th percentiles, and the maximum value.

The integers in the input will be sampled from a gamma distribution. Because of the characteristics of gamma distributions, as the input size increases, the number of unique values will grow slowly, and there will be an increasing number of duplicates, yet there is no absolute upper limit on the values. This will make the input a good candidate for a hash$-$based counting sort.

You will compute the five$-$number summary with each of the following methods, and benchmark the time taken for each method:

$1)$ Use std::sort

$2)$ Use quickselect $3$ times, then calculate the min and max separately

$3)$ Modify quickselect to recurse if any of the $5$ values are in the subrange

$4)$ Use a modified counting sort that uses hashes

For method $2,$ find the median first. Then, on the same vector that's already partitioned around the median, call quickselect on the left half to find P$25$ and on the right half to find P$75.$ Then, search the part of the vector below P$25$ for the min and above P$75$ for the max.

For method $3,$ modify quickselect's recursive function to take a short list of keys rather than just one key. If you refer to p$\mathrm{.}322$ in the textbook, you can replace the parameter int k with a small vector or list. Then rewrite the recursive portion so that quickselect calls itself on one or both sides, depending on whether there are positions you're searching for on both sides or only one.

Each method should print the header from the input file, followed by $5$ lines stating the minimum, each quartile, and the maximum.

Here's an example showing the output from the sample input file:

Male elephant seal weights

Min: $5069$

P$25$: $5796$

P$50$: $6129$

P$75$: $6548$

Max: $9218$

For counting sort only, also include the number of unique values. For the sample input, it would look like:

Unique: $787$

To simplify determining which position you're looking for, I$\text{'}$m going to keep input sizes divisible by $100.$ So then, in a sorted list of $1000$ elements, P$25$ is the $250$th element, P$50$ is the $500$th$,$ P$75$ is the $750$th$,$ etc.

You must submit the following files:

main.cpp$,$ which reads the input from file and passes the header and data to each method.

StdSort.cpp$,$ containing the function void stdSort $($const std::string & header, std::vector data$)$

StdSort.hpp$,$ containing the necessary prototypes.

QuickSelect$1.$cpp$,$ containing the function void quickSelect$1($const std::string & header, std::vector data$)$

QuickSelect$1.$hpp$,$ containing the necessary prototypes.

QuickSelect$2.$cpp$,$ containing the function quickSelect$2($const std::string & header, std::vector data$)$

QuickSelect$2.$hpp$,$ containing the necessary prototypes.

CountingSort.cpp$,$ containing the function void countingSort $($const std::string & header, std::vector data$)$

CountingSort.hpp$,$ containing the necessary prototypes.

InsertionSort.cpp$,$ which may be blank if you wrote insertion sort directly in your QuickSelect files.

InsertionSort.hpp$,$ which may be blank if you wrote insertion sort directly in your QuickSelect files.

Yes, the functions all take the same parameters. They only take a reference to the header, which will just be printed out, and a copy of the data, which will be sorted or partitioned around several points depending on the method used.

The data is passed by value, since the function will sort the vector it's passed, and most of the methods are in$-$place.

You will need to write your own helper functions for each. In particular, for quickSelect, you will need to write the recursive quickSelect and use the function I require as a wrapper.