Compare sorting algorithms by counting their work
Three steps, the way the exam actually works: work through the lab, write down your own measurements, then answer a 6-point free response. What you recorded goes to the grader with your writing, so a conclusion that does not follow from your own numbers will cost you the point — exactly as it would with a real reader.
Run the investigation
- 1Set the array size to 14 and run bubble sort to completion. Record the number of comparisons it reports.
- 2Without changing the array size, run merge sort and record its comparison count.
- 3Increase the array size to roughly double it, then run bubble sort again and record the new comparison count.
- 4Run binary search on the sorted array and record how many comparisons it needs.
Booting the lab…
Record what you measured
These are your numbers, not ours. The grader sees them, so your conclusions have to follow from what you actually recorded.
| Bubble sort comparisons at n = 14 | |
|---|---|
| Merge sort comparisons at n = 14 | |
| The larger array size you used | |
| Bubble sort comparisons at that larger size | |
| Binary search comparisons |
Answer the free response
You measured the work each algorithm actually performs. (a) Compare your two comparison counts at n = 14 and state which algorithm did less work. Give the Big-O complexity of each and explain what that notation describes. (b) Using your two bubble-sort measurements at different array sizes, show that the growth is consistent with a quadratic rather than a linear cost. Support this with the ratio of your counts. (c) Explain why merge sort achieves O(n log n) by describing what the algorithm does at each level of recursion and how many levels there are. (d) Your binary search finished in very few comparisons. State its complexity, and identify the precondition that must hold before it can be used at all.
Sign in to have this graded and saved to your progress.