We can also analyze the Simple Sort and Insertion Sort to find general formulas that describe their time efficiency. Let's review the steps we used in the last lesson.
- First, we choose four numbers which represented a worst-case ordering. (Remember, the worse-case is the order which requires the most swaps and comparisons to sort).
- Next, we sorted these numbers and kept track of the swaps and comparisons needed at each step.
- Finally, we examined our results to find a regular pattern that could be represented by a formula.
Using these same steps, you will find general formulas for the Simple Sort and the Insertion Sort in this lesson. We will begin with the Simple Sort.
Worst-Case Analysis of Simple Sort
Worst-Case Analysis of Insertion Sort
Now that you have your tables complete, you should be able to see some regular patterns. You will use this information in the review questions to derive formulas for the number of comparisons, copies, and swaps these sorts need to order items in the worst case.