Java Reference
In-Depth Information
of comparisons will be n 1, which is the number of times the outer
for
loop
executes. Thus, the cost for Insertion Sort in the best case is (n).
While the best case is significantly faster than the worst case, the worst case
is usually a more reliable indication of the “typical” running time. However, there
are situations where we can expect the input to be in sorted or nearly sorted order.
One example is when an already sorted list is slightly disordered by a small number
of additions to the list; restoring sorted order using Insertion Sort might be a good
idea if we know that the disordering is slight. Examples of algorithms that take ad-
vantage of Insertion Sort's near-best-case running time are the Shellsort algorithm
of Section 7.3 and the Quicksort algorithm of Section 7.5.
What is the average-case cost of Insertion Sort? When record i is processed,
the number of times through the inner
for
loop depends on how far “out of order”
the record is. In particular, the inner
for
loop is executed once for each key greater
than the key of record i that appears in array positions 0 through i1. For example,
in the leftmost column of Figure 7.1 the value 15 is preceded by five values greater
than 15. Each such occurrence is called an inversion. The number of inversions
(i.e., the number of values greater than a given value that occur prior to it in the
array) will determine the number of comparisons and swaps that must take place.
We need to determine what the average number of inversions will be for the record
in position i. We expect on average that half of the keys in the first i 1 array
positions will have a value greater than that of the key at position i. Thus, the
average case should be about half the cost of the worst case, or around n
2
=4, which
is still (n
2
). So, the average case is no better than the worst case in asymptotic
complexity.
Counting comparisons or swaps yields similar results. Each time through the
inner
for
loop yields both a comparison and a swap, except the last (i.e., the
comparison that fails the inner
for
loop's test), which has no swap. Thus, the
number of swaps for the entire sort operation is n 1 less than the number of
comparisons. This is 0 in the best case, and (n
2
) in the average and worst cases.
7.2.2 Bubble Sort
Our next sorting algorithm is called Bubble Sort. Bubble Sort is often taught to
novice programmers in introductory computer science courses. This is unfortunate,
because Bubble Sort has no redeeming features whatsoever. It is a relatively slow
sort, it is no easier to understand than Insertion Sort, it does not correspond to any
intuitive counterpart in “everyday” use, and it has a poor best-case running time.
However, Bubble Sort can serve as the inspiration for a better sorting algorithm that
will be presented in Section 7.2.3.
Bubble Sort consists of a simple double
for
loop. The first iteration of the
inner
for
loop moves through the record array from bottom to top, comparing
adjacent keys. If the lower-indexed key's value is greater than its higher-indexed
