Questions:

  1. For the Simple Sort, how many comparisons were needed at each step to sort four numbers? How would this value change if you were sorting five numbers? six numbers?   [Answer]

  2. How can you write the relationship between the number of comparisons the Simple Sort requires at each step and n, the number of items to be sorted?   [Answer]

  3. What value do you need to know to find the total number of comparisons the Simple Sort requires in the worst case? From looking at the example, what do you think this value might be?   [Answer]

  4. Write a formula which computes the total number of comparisons the Simple Sort needs in the worst case. Use the expressions you found for the number of comparisons at each step and the total number of steps.   [Answer]

  5. How many copies were needed at each step of the Simple Sort? If you were sorting five numbers, would the number of copies per step change?   [Answer]

  6. Write a formula which computes the total number of copies the Simple Sort needs in the worst case. Use the expressions you found for the number of copies at each step and the total number of steps.   [Answer]

  7. What is the relationship between the number of comparisons the Insertion Sort requires at each step and the current step of the algorithm? Is this pattern similar to anything you have seen in the analysis of the Selection Sort?   [Answer]

  8. Use the analysis of the Selection Sort as an pattern for writing a formula which calculates the total number of comparisons the Insertion Sort needs in the worst case.   [Answer]

  9. Since the answers for the number of comparisons and the number of swaps needed are the same at each step of the Insertion Sort, do you think you can use the formula from question 6 to compute the number of swaps the Insertion Sort needs in the worst case?   [Answer]