Complexity of Programs 3075.3.4 An Algorithm Illustrating Nested Repetition
Now look at the entire BubbleSort I algorithm. It is easy to see that after the first pass,
the largest element has reached the end of the list. This effect appears to be the origin of
the name "bubble sort"-the larger elements seem to bubble down through the list. After
the second pass, the second largest element is in place, and so on. After pass N - 1, the
second smallest element has bubbled down to position 2, and the smallest element is left
in position 1. So, in particular, at most N - 1 passes are needed.
BubbleSort I can be improved. Since the largest element bubbles to List[N] in the first
pass, there is no reason to look at the last position again. On the second pass, the second
largest element bubbles to List[N - 1], and that position need not be examined again, and
so on.
INPUT: A list of N distinct integers List[lI], .. ... List[N]
OUTPUT: List[l1], .. ... List[N], with values in increasing orderBubbleSort-II(List, N)- for Pass= ltoN-ldo
- Limit = N - Pass
3. for Position = 1 to Limit do
- if (List[Position] > List[Position + 1])
- Swap(List[Position], List[Position + 1])
In BubbleSort II, the first pass through the loop in lines 3 through 5 still performs
N - 1 comparisons. In the second pass, however, the size of the list is reduced by 1, so the
second pass performs N - 2 comparisons. The third pass reduces the number of elements
considered again by one and performs N - 3 comparisons. Here, the function F 1 (Bi) =
i - 1. So, the total number of comparisons is equal to
N-i
i = 1 + 2+3 +... + (N- 2) + (N- 1) = N(N-- 1)/2
i=1Example 1. For the slightly optimized BubbleSort II algorithm, count the number of
Swap's.
(a) If the input list is out of order in the way shown here:
List[l] > List[2] > List[3] > ... > List[N - 1] > List[N]the algorithm makes exactly N • (N - 1)/2 calls to Swap.
(b) If the input list is arranged so that
List[l] < List[2] < List[3] < ... < List[N - 1] < List[N],
the algorithm makes no calls to Swap.