Objectives:

Practice using quick sort from modules.

Investigate the recursion limit of Quick Sort.

Visualize the results of your analysis.

Use git features such as commit and clone to write and read from your repository.

Material from:

Syllabus and Program Guidelines.

Material from Chapter 7 of Weiss Book.

In FHsort.java add the static mutator FHsort.setRecursionLimit(int) which you will use to change this limit to any int value in the range of 2 to 300. In this project, the goal is to find the optimal recursion limit arrays of various sizes.

What's different about this project?

Unlike previous projects, this project is computationally expensive, so make sure to give your machine enough time to run all the test cases.

Client Requirements

Write a test file that investigates the recursion limit of arrays of various sizes. Your test file must be in a separate class than FHsort class, which means a new .java file.

Your test must show the following:

Investigate all recursion limits from 2 to 300 in steps of 2. For example: 2, 4, 6, 8 ...

Run them on different size arrays from 20,000 up to the largest you can get in your computer (you should be able to get it up to close to 10 million or more) with at least 20 intervals. NOTE: Make sure that for each array size you use the same randomly generated numbers to test the different recursion limits.

Run each test case at least 3 times. That way you can filter out non-significant differences in run time.

Provide a table that summarizes the results. Share a table of your results in either HTML or Excel* format. If you are not able to access either, than your table should be a well formatted plain-text file, such as Comma Separated Value (CSV) (Links to an external site.)Links to an external site. file. Your file should only be in one of these three formats (for example, do not submit a Microsoft document).

Augment your results with a diagram that visualizes the trends you found as you changed the recursion limit and array size. Include the following:

An automatically generated graphical representation of your table (i.e. the raw data). Why "automatic"? Hand-drawn representations are inaccurate, especially at the scales we are dealing with. To avoid use a data visualization application or library*;

A line graph (Links to an external site.)Links to an external site. of the impact of recursion limit (x-axis) on different array sizes in terms of runtime (y-axis). Include axis labels and a legend for your graph.

A graph of the different line-plots over-laid. This means that at least one of your graph diagrams must have all the array sizes overlaid. NOTE: Don't forget to annotate this graph with any interesting patterns you discover!

A second graph where you filtered and zoomed* to a particular range of interest for recursion-limit vs array size. NOTE: Once you identify an interesting pattern for potential range of recursion limit where the optimal may lie, create a second graph that displays only the data for that range. To decrease the clutter in your graph, try filtering out the plot that seem to have similar patterns.

How do I zoom in? This step requires a re-plot using a subset of your results. If your data is in a table format, this means that you select a subset of the columns and rows for your second plot. Zooming does not mean that you magnify the first graph via a pixel editing application such as paint.

Annotations your graph(s) with your findings (such as optimal recursion limit). This means manually circling and adding comments that describe the range of interest you describe in your observations.

A snapshot of your two (or more) plots visualizing the table.

Include graph along with the rest of your implementation under the resources folder in your assigned repository.

Comment on the results. For example, describe:

the range that seems to be minimal (and flat);

observations whether there are fluctuations in the runtime.

As usual, your results and comments must be outside your test file in the RUN.txt file.

FAQ: Why is my repository empty?

Unlike previous projects, your repository is empty. You will be creating a test file and submitting it with your findings.

FAQ: How do I submit my work?

*FAQ: I don't like Excel. What other graphing libraries can I use?

Gunplot (Links to an external site.)Links to an external site. and and data visualization libraries based on D3.js (Links to an external site.)Links to an external site. are two that I recommend. The later group is based on D3.js which is currently one the most popular libraries used to create HTML based visualizations of data.

Have another preferred library? Post your recommendation for this weeks discussion forum titled: Answer the Instructor's Weekly Questions Here -> What graphing libraries or applications do you prefer?

As usual in order to receive full credit on this assignment, your program must:

Follow all Program Guidelines, see Modules for the guidelines.

Meet all client requirements.

Include the following in your lab submission:

The source code: the listing of your classes investigating the recursion limit of quick sort. under the src folder. Note: include all classes needed to successfully compile and run your test such as FHsort.java

Comment all class and all method. Then, generate Javadocs and include it in your submission.

Run output sample(s) and visualization of your table under the resource folder.

A brief description of all files submitted: in a plain-text file called README.txt