Task 4: Discussion of the Sorts

Write your answers in DISCUSSION.md, under the heading for each part. Use the numbers you measured. When you say an algorithm does more work than another, show the numbers that say so.

Part I: Counting accesses and mutations

The quadratic sorting chapter counts comparisons and swaps. Your MeasuredArrayList counts accesses and mutations. These are not the same thing.

For SelectionSort, BubbleSort, and InsertionSort as you wrote them, how many accesses and mutations does one comparison cost? How many does one swap (or one shift) cost? Use your answer to predict the mutations each of the three sorts makes on 4,000 values in reverse order. Then run SortingAlgorithmDriver and compare your prediction with the row for descending.data.

Part II: Profiling the sorts

Run SortingAlgorithmDriver with:

scripts/run.sh sorts.SortingAlgorithmDriver

It reads the first SIZE values of each data file in resources/, sorts them with every sort, and prints a report like this one (yours will show your own sorts):

Data file         Algorithm       Sorted?  Accesses     Mutations    Microseconds

ascending.data    Null Sort       false    0            0            1
ascending.data    Gnome Sort      true     15230058     5074020      26742
ascending.data    Selection Sort  not implemented
...

“Sorted?” says whether the result is in order. “Accesses” and “Mutations” are the counts your MeasuredArrayList made during the sort. “Microseconds” is how long the sort took. Time varies from machine to machine and from run to run, so use it only to compare runs on the same machine. Run the driver several times.

There is a discrepancy between the report and what the notes tell us to expect. In some rows, the numbers do not match what we know about the algorithm and the data. This comes from an intentional mistake in how the experiment is set up. The mistake may be in the code, in the data, or in both.

Use the counts to find the discrepancy. Then use a debugger to step through the code and the data until you find the mistake. In your answer, describe the mistake and the steps that led you to it. Then describe the experiments you ran and what they show about the relative performance of the sorts. Include the numbers: data file, SIZE, counts, and times. You may change SIZE to run the sorts on more or fewer values.

Do not fix the mistake. Do not change the driver, except SIZE, and do not change the data files. Find the mistake on your own: do not ask the teaching staff whether your finding is the one I mean, and do not post about it on the course discussion board.