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:- Compared the wall clock performance of several O(n2) sorting algorithms
- Discovered the weakness of asymptotic analysis.
- Presented these findings in a written document.
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.- Implement, debug, and test the following sorting algorithms.
Bubble(A) Input: an array A, with comparison operator < on the elements and size
0 ≤ A.size()Output: A ordered by the < operator, smallest element first.- n ← A.size()-1
- repeat
- swapped ← false
- for i ← 1 to n do
- if A[i-i] > A[i]
- Swap(A[i-1],A[i])
- swapped ← true
- n ← n - 1
- until not swapped
Insertion(A) Input: an array A, with comparison operator < on the elements and size
0 ≤ A.size()Output: A ordered by the < operator, smallest element first.- i ← 1
- while i < A.size()
- j ← i
- while j > 0 and A[j-1] > A[j]
- Swap(A[j], A[j-1])
- j ← j - 1
- i ← i + 1
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:
- Introduction: provide a brief introduction to the experiment.
- Methods: describe what you did and the conditions when you did it. This includes a description of the timing framework as well as the macihne on which the experment was conducted.
- Results: present the results of your experiments, without commentary.
- Discussion: discuss what you found and draw conclusions.
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.