Develop JUnit tests for five standard sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Merge Sort.

Implement the above sorts. Test your code.

Measure your codes performance over increasingly large datasets.

Your sorting project will contain the following classes:

SortInterface interface (provided)

Sort class, which implements the interface class

SortTest class, JUnit test cases for your Sort methods.

Profiler class, which contains your measurement code

It is critically important that:

The class that measures runtime execution be named Profiler.

Your Profiler class has a main method.

You report on your measurements (for all sorts, over all specified data sizes) in a document called SortResults.pdf.

Measuring Average Sort Execution Time

Develop a class called Profiler that contains code to measure the performance of your Sort methods over increasingly large datasets.

For each sort method you should measure its:

execution time given a random dataset for each of the specified data sizes.

execution time given a sorted dataset of random elements for each of the specified data sizes

In order to see how long each sorting algorithm takes to run, you should measure the runtime of each method on both random and sorted lists of sizes 5, 10, 50, 100, 200, 500, 1000, 5000, 10000, 50000, 75000, 100000 and 500000. You can get a random list using the java class Random, located in java.util.Random (Links to an external site.)Links to an external site.. NOTE: It will take several hours to run these tests.

To measure the speed of your sorting algorithms, you should use the System.currentTimeMillis() (Links to an external site.)Links to an external site. method, which returns a long that contains the current time (in milliseconds). Call System.currentTimeMillis() before and after the algorithm runs, and subtract the two times. Unfortunately, using currentTimeMillis before and after a function only gives an accurate time estimate if the function takes a long time to run. Since running some sorting algorithm on a list of size 1000 will take a very short time, you will need to do something like the following which calculates an average execution time:

long startTime, endTime; double duration; Random randomGenerator = new Random(); Sort sorter = new Sort(); startTime = System.currentTimeMillis(); for( int i = 0;i  list = new ArrayList( ); for ( int j = 0; j  
You will have to experiment with different values for numberOfIterations. It will need to change depending upon the size of the list and the algorithm.
 
You might notice that there is some non-sorting work done in the above algorithm. Setting up the list before each sort can take place takes a small amount of time, but it adds up. You can easily check for yourself:
 
 long overheadStart, overhead = 0; for ( int i = 0; i  list = new ArrayList( ); for ( int j = 0; j  
You should subtract this setup time from your algorithm running time, to get more accurate results. 
 
create a doc containing:
 
running times for all 5 algorithms for lists of 5, 10, 50, 100, 200, 500, 1000, 5000, 10000, 50000, 75000, 100000 and 500000. Be sure to subtract out the overhead time costs! You should include as inputs: pre-sorted ascending and presorted descending lists as well as unordered lists for each list size in these tests.
 
 Graphically compare the results of one of Bubble Sort, Selection Sort, or Insertions Sort and one of Shell Sort, Merge Sort.
 
Explain what you see in the graph.