In our last lesson we saw the measured time efficiency of a sorting algorithm can change depending upon the order of the items being sorted. Because of this, it is common to measure the performance of sorting algorithms using the worst possible conditions or the worst case. The worse case is the particular order of items that will require the greatest number of comparisons and swaps to sort.
The measured time efficiency of an algorithm can also change as we increase the number of items sorted. For example, what would happen if we used our sorting algorithms to order a million numbers rather than seven? Which algorithm would be the most time-efficient? How could we measure the time efficiency of the sorts? To answer these questions, we could count the number of swaps and comparisons, but this would be extremely tedious. What we really need is a way of describing the number of swaps and comparisons with a formula. With such a formula we could easily recompute the time efficiency of the algorithm each time we varied the number of items to be sorted. The animation below demonstrates how to derive a formula which describes the worst case performance of the Selection Sort.
Once again, here are the formulas we derived for the number of comparisons and swaps the Selection Sort requires in the worst case. The number of items to be sorted is represented by n.
# of swaps = (n-1) |
Notice that the formula for the number of comparisons is a summation, a series of terms added together. Each term represents the comparisons from one step of our sort. As we increase the number of items to be sorted, we also increase the number of terms in our formula. For example, suppose we were sorting six items and we wanted to know the maximum number of comparisons needed to sort them (i.e. the worst case). Here is how we would find the answer.
When sorting six items with the Selection Sort, the algorithm will need to perform 15 comparisons in the worst case. Since we computed the performance in the worst case, we know that the Selection Sort will never need more than 15 comparisons regardless of how the six numbers are originally ordered.
- First, we write out the correct number of terms in our formula. Remember that n = 6 in this example. The last term in our formula is (n - 5) because this is equal to 1.
# of comparisons = (n-1) + (n-2) + (n-3) + (n-4) + (n-5)
- Now we substitute 6 for n and sum the values.
# of comparisons = (6-1) + (6-2) + (6-3) + (6-4) + (6-5)
# of comparisons = 5 + 4 + 3 + 2 + 1
# of comparisons = 15