Homework 3, O(n2) sort comparison.

Short Description:

Perform a wall clock timing analysis of several O(n2) sorts, describe the results and discuss the weakness of asymptotic analysis.

Goals

When you finish this homework, you should have:

Formal Description

Using the framework from the alternative activity, compare the wall clock performance of selection sort, insertion sort and bubble sort. Present graphical representation of these results and summarize your experiment.

After you have implemented these algorithms, perform a series of timing experiments, counting the number of comparisons, data moves and total time spent in each sort. You should sort between 1,000 and 10,000 elements that have been randomly generated on the range [0 to 1,000,000] ten times each.

In addition, test selection sort as implemented in the example code.

Produce a table showing the summary of your results. This should incldue your two sorts, along with selection sort and should present the average time, comparisons, and data moves for each different array size. Produce several graphical depictions of this table. I would use excel and generate a pivot table to do this. If you need assistance, please ask.

Make sure that your graphs are well labeled and clearly present the results.

Write a report describing your findings and interpreting the results. Your report should follow the IMRD format:

Make sure that you include a discussion of the difference between asymptotic time and wall clock time in measuring performance. Does each have a purpose?

Notes:

As always you must credit any collaborators, including AI and describe the amount of AI used in completing this homework.

I do not believe that there are any errors in the given algorithms, but if any exist, you should correct them and implement sorting algorithms that pass the check routine.

If you wish to test any other versions of O(n2) sorts, please do so and include your results in your final report. We will do O(n log2n) sorts in the next homework.

Required Files

A single document containing your data and results.

Submission

Submit the assignment to the D2L folder Homework 3 by the due date.