Part $1($Implementation$)$:

Implement three sorting algorithms rst and then run the provided time testing code to compare the

performance of the algorithms. Here is the list of les that have unimplemented methods that you need

to nish:

$1.$ InPlaceSelectionSort.java

$2.$ InPlaceInsertionSort.java

$3.$ InPlaceHeapSort.java

$6.$ Test les $($using Junit$)$ for InPlaceSelectionSort, InPlaceInsertionSort, InPlaceHeapSort, Merge$-$

Sort.java, and QuickSort.java. A sample test le for Select Sort InPlaceSelectionSort.java has

been created for you. Feel free to create more test cases as you see t$.$ To test other sorting

algorithms, you can copy that le$,$ then modify the code to instantiate a dierent sort in method

setup$()).$

Important Note:

$$ Don't cast the generic type E to int in your code. We will test with data other than int type.

Part $2($Running Time Analysis$)$:

This part of the assignment is provided to help you analyze the performance of the aforementioned

algorithms. The required code is provided for you. Just use it$!$

After implementing the sorting algorithms and testing them with small array, you could test how long

it will take to sort random numbers. The time testing code has been already implemented in SortTim$-$

ing.java. It will take somewhere between $10-15$ minutes $($although it depends on your machine$)$ to nish

all time testing.

Read the code carefully and understand what it does. You might want to run a certain type of sort rst$,$

not all of them at once. You can do this by commenting and uncommenting part of the codes. Then

run the main method. You will see the progress of the code as it runs through all $5$ sorting algorithms

for dierent data size, from $1,000$ to $100,000$ elements. It measures the time in million second for each

sort, and output the result to the console and to a le called output.txt$.$

After the running is complete, load the data in output.txt to Excel or other tools to plot the following

chart. You need to save the data from output.txt and the two graphs in ONE pdf le$.$ Create a line

graph of the time testing for all $5$ sorting algorithms :

$$ The horizontal $($x$)$ axis should be "input size".

$$ The vertical axis $($y$)$ should be "time in ms$".$

$$ The title should be "Running Time of $5$ Sorting Algorithms".

Create a line graph of the time testing for the three fast sorting algorithms: MergeSort, QuickSort,

InPlaceHeapSort :

$$ The horizontal $($x$)$ axis should be "input size".

$$ The vertical axis $($y$)$ should be "time in ms$".$

$$ The title should be "Running Time of $3$ Fast Sorting Algorithms".