Write a JAVA program that measures the running time of different sorting algorithms such as heap sort, in-place quick sort and merge sort for 10,000 randomly generated integer numbers.

Since you are using random numbers, you need to repeat your experiments 10 times to be able to compute the average running time. So you are required to generate 10,000 integers, and compute the minimum, maximum and average time required to sort the data. Your generated random data should be between 0 to 100,000.

Hint

Heap sort, in-place quick sort and merge sort algorithms are available in the book and the companion website of the book.

You are NOT required to implement the algorithm with a generic type. It is enough for this assignment that your sorting algorithms work for integer data only.

Use the following code to compute the running time:

long startTime = System.currentTimeMillis(); // record the starting time

/*(run the algorithm)*/

long endTime = System.currentTimeMillis(); // record the ending time

long elapsed = endTime - startTime; // compute the elapsed time

Input

This program does not need to input any data from the console, instead it should provide the input to the algorithm using a random generation method.

Output

You need to provide a table as follow for the input and print the running time in the right cell of this table.

Algorithm name Min Average Max

Heap-Sort

In-place Quick-Sort

Merge-sort

Other requirements

? Your project and file name should be DataStructuresProject, fifthAssignment respectively.

? You must deliver a working code only, otherwise your code will not be marked.

? You are required to submit only one .java file otherwise your code will not be marked.

? You are only allowed to use the sorting algorithm that is provided in your book. No any other implementation is allowed.