Here is the project for the Data Structures and Algorithms course. You are required to optimize the quicksort program provided above based on the following issues.

Starting with the C$++$ code for Quicksort given in this chapter, write a series of Quicksort implementations to test the following optimizations on a wide range of input data sizes. Try these optimizations in various combinations to try and develop the fastest possible Quicksort implementation that you can.

$($a$)$ Look at more values when selecting a pivot.

$($b$)$ Do not make a recursive call to sort when the list size falls below a given threshold, and use Insertion Sort to complete the sorting process.

Test various values for the threshold size.

$($c$)$ Eliminate recursion by using a stack and inline functions.

A zip file which includes:

A cpp file that includes four implementations of the quicksort algorithm: the original implementation,

the optimized sorting algorithm after $($a$),$ the sorting algorithm optimized after both $($a$)$ and $($b$),$ and the sorting algorithm optimized after $($a$),($b$),$ and $($c$).$

A text file describing the runtime of four programs in milliseconds.

for example: original:

$3248759$ms

$($a$)$ :

$3000000$ms

$($b$)+($a$)$:

$2900000$ms

$($c$)+($b$)+($a$)$ : $2800000$ms

Some screenshots of the results of your program's execution.

Your program should sort a dataset of one million entries.

You need to generate a batch of random data, use the four quicksort programs you implemented to sort this data.

If your dataset is not one million entries, then I will deduct $40$ points from your score.