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.

  1. 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).

  2. Next, we sorted these numbers and kept track of the swaps and comparisons needed at each step.

  3. 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

Use the Simple Sort to order the numbers on the right. For each step, keep track of the number of copies and comparisons needed. Then enter your answers in the boxes below to see if they are correct.

Worst-Case Analysis of Insertion Sort

Use the Insertion Sort to order the numbers on the right. For each step, keep track of the number of swaps and comparisons needed. Then enter your answers in the boxes below to see if they are correct.

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.