Now that we have formulas to describe the worst case time efficiency of our sorting algorithms, we can see how the algorithms will perform as we increase the number of items to be sorted. First, let's review our formulas. Notice that the formulas for swaps have been converted to copies by multiplying by 3. This allows us to correctly compare Simple Sort with the other two sorts.
Algorithm | Comparisons | Copies |
Simple Sort | n * (n-1) | n |
Insertion Sort | (n-1) + (n-2) + ... + 1 | 3 * [(n-1) + (n-2) + ... + 1] |
Selection Sort | (n-1) + (n-2) + ... + 1 | 3 * (n-1) |
Using our formulas, we will compute the number of comparisons and copies needed to sort several lists of items. The number of items in each list increases by a power of ten.
Comparisons Required |
# of Items | Simple Sort | Insertion Sort | Selection Sort |
10 | 90 | 45 | 45 |
100 | 9,900 | 4,950 | 4,950 |
1,000 | 999,000 | 499,500 | 499,500 |
10,000 | 99,990,000 | 49,995,000 | 49,995,000 |
From our table of comparisons, we can see two important facts. First, the Simple Sort always requires twice as many comparisons as the Insertion and Selection Sorts. This means we can rewrite the formula for these sorts as follows: (n * (n-1)) / 2. This expression is much easier to use than the summation (n-1) + (n-2) + ... + 1, especially when n is large.
Second, all three sorts require a tremendous number of comparisons as the number of items increases. In fact, we can see with the Simple Sort that the number of comparisons is very close to n^{2}. Take another look at the formula you derived for the number of comparison the Simple Sort requires in the worst case. If we multiply the n into the parentheses, the formula becomes n^{2} - n. Now you see why our total comparisons is very near n^{2}. You can also see why the number of comparisons needed is growing so quickly.
Copies Required |
# of Items | Simple Sort | Insertion Sort | Selection Sort |
10 | 10 | 135 | 27 |
100 | 100 | 14,850 | 297 |
1,000 | 1,000 | 1,498,500 | 2,997 |
10,000 | 10,000 | 149,985,000 | 29,997 |
Now let's compare the number of copies each algorithm requires. Notice how quickly the number of copies required by the Insertion Sort is growing. This makes us suspect that the formula for the Insertion Sort contains an n^{2} term. In fact, the formula does contain such a term, but we must rewrite the formula to see it. Using the relationship we discovered earlier, we can replace the summation (n-1) + (n-2) + ... + 1 with (n * (n-1)) / 2 and simplify.
# of copies = 3 * [(n-1)
+ (n-2) + ... + 1] |
The simplified formula shows the n^{2} term that we suspected. Notice that the other two formulas only have an n term rather than a n^{2} term. This is the reason that they grow slowly as the number of items increases.