3.2 BUBBLE SORT 65to execute the for loop N 1 times. This indicates that an input data set that
is in the reverse order does lead to the worst case.^1
How many comparisons are done in this worst case? We have said that the
first pass will do N 1 comparisons of adjacent values, and the second pass
will do N 2 comparisons. Further examination will show that each succes-
sive pass reduces the number of comparisons by 1. This means that the worst
case is given by the formula
■ 3.2.3 Average-Case Analysis
We have already said that in the worst case, there would be N 1 repetitions
of the inner for loop. For the average case, we will assume that it is equally
likely that on any of these passes there will be no swaps done. We need to
know how many comparisons are done in each of these possibilities. If we stop
after one pass, we have done N 1 comparisons. If we stop after two passes,
we have done N 1 + N 2 comparisons. For now, let’s say that C(i) will
calculate how many comparisons are done on the first i passes. Because the
algorithm stops when there are no swaps done, the average case is found by
looking at all of the places bubble sort can stop. This gives the equation
(^1) This case does the largest number of comparisons and swaps, but because we are only
interested in counting the number of comparisons, there are other data sets that will
lead us to this worst case. The reader should be able to show that any list of elements
with the smallest element in the last position, for example, will also produce this worst-
case result. Can you find any others?
WN() i
i=N–1
1
∑ i
i=1
N–1
∑
()N– 1 N
2
----------------------- N
(^2) – N
2
=== =------------------
WN()≈^12 --N^2 =ON()^2
AN() N-------------^1 – 1 Ci()
i=1
N–1
= ∑