Purpose
The purpose of this assignment is to get you to critically examine the code for some basic sorting routines operating on a linked list and create a simulation that will demonstrate how much "work" each routine does. This will not be much of an exercise in object oriented design, but don't take that to mean you can throw everything you know about OO out the window.
Specifics
In this assignment you will gather data on how many operations different sorting routines perform. More specifically, you will count the following for each sorting routine:
• the number of data comparisons made
• the number of loop control comparisons made
• the number of assignment operations involving data
• the number of assignment operations involving loop control
• "other" operations (operations that don't fall in one of the above categories)
• the total number of operations (the sum of the above)
• NOTE: comment in your code each thing you count
The above measurements will be taken on:
• an already sorted linked list
• a descending sorted linked list
• a linked list contain random data
• NOTE: You must utilize a doubly linked list that is circular and uses a dummy head node. Add methods to your list as you deem necessary (you do NOT have to implement the List interface)
You will generate each of these linked lists with the following number of BigInteger elements:
• 500
• 1000
• 5000
• 10000
• NOTE: you can choose more values than this if you wish
The sorting algorithms examined will be:
• "Smart" Bubble Sort (stops when list is sorted)
• Selection Sort
• Insertion sort that shifts data down (which is how you do it with an array)
• Insertion Sort that cuts node to insert out of list and pastes it in spot it needs to go in sorted part of list
• NOTE: it is permissible to place these sort routines as methods that belong to your linked list class for the purposes of this assignment
• EXTRA CREDIT: include additional sort routines
Be sure and make copies of the original lists (as necessary) so that each routine is operating on the same data.
Construct and graph a separate curve for each algorithm for
• data assignments
• total operations
for each list type (sorted, descending sorted, random). You should have a total of 6 graphs for the above items (note that there will be 3 other graphs to make in addition to the 6 -- those are specified below):
1. A graph that shows data assignments for all sorting routines for sorted lists
2. A graph that shows data assignments for all sorting routines for descending lists
3. A graph that shows data assignments for all sorting routines for random lists
4. A graph that shows total operations for all sorting routines for sorted lists
5. A graph that shows total operations for all sorting routines for descending lists
6. A graph that shows total operations for all sorting routines for random lists
You must use a spreadsheet/graphing program for your graphs.

Your program should write all the raw data (which you will use to construct the graphs) to a text file called sort_results.txt -- the format you use is up to you, but make it so someone else (the grader) can easily read the data and understand what it represents. Your program does not require input (either from a file or from the keyboard).
Also, use System.nanoTime() to time each sort. Report these results to your output file as well and create graphs to accompany the data. This will add 3 more graphs to what you submit for a total of 9 (graphs for sorted, descending, and unsorted lists). Format the nano time results to be in seconds with nine digits of precision to the right of the decimal point (printf makes this easy). To ensure more accurate timings, check the time for each sort on sorts without code that counts operations. This means you will have to versions of each sort. One version will be just sort code, the other will include counting code.
For extra credit (15 points), generate a second output file that contains comma delimited data (a .csv file) that can be loaded into a spreadsheet program. The purpose of this second file is to make it easy to build your graphs.
To Turn In:
This assignment must be submitted in working order by 11:59:59pm Wednesday, October 19. Submit a *ZIP* file with:
1. your source files
2. your output file (sort_results.txt)
3. your graph/spreadsheet file(s) (add this to your jar) *in .pdf format*
4. if you perform the extra credit, be sure and note that at the top of the source file that contains the extra credit code; also include the .csv file created from running your program with the extra credit.
The grader should be able to open your zip file, compile your code, and run your program from the command line using javac and java version 1.6 or greater (so make sure you try this yourself before you submit). No input should be required on the part of the user (grader) for this program. Name your zip file with your last name, followed by the first initial of your first name, followed by hw2 (e.g. armstrongehw2.zip or capaulthw2.zip)
Finally, name your tester file (the one that contains the main method) SortTester.