Complexity of Programs 305is a command to repeat operation S over and over, once with i = 1, once with i = 2, ....,
and once with i = N. If N < 1, then operation S is not executed at all. (See Section 1.8.1
for further discussion of this command.)INPUT: A list of N distinct integers List[l]... List[N]
OUTPUT: The same integers rearranged so that the values of
List[l] .... List[N] are in increasing orderBubbleSort-I(List, N)- for Pass=ltoN-ldo
2. for Position = I to N - 1 do
- if (List[Position] > List[Position + 1]) then
- Swap (List[Position], List[Position + 1])
The BubbleSort I algorithm contains two nested loops. We will first consider the inner
loop, or lines 2 through 4. This loop compares adjacent elements in the list, and whenever
it finds a pair that is out of order, it interchanges them. In the following example of a
four-element list, there are three adjacent pairs, so the algorithm interchanges at most three
times. We trace the results of lines 2 through 4 the first time they are executed-that is,when Pass = 1. We assume that a < b < c < d is the final order.
Pass = 1
c b d a Initial list
c b d a Compare first pair
b c d a Out of order, so swap
b c d a Compare second pair
b c d a In order; don't swap
b c d a Compare last pair
b c a d Out of order, so swap
b c a d The final list for Pass = 1The for statement causes lines 3 and 4 of the program, called the body of the loop, to
be executed N - 1 times, the first time with the value of Position equal to 1, the second
time with the value of Position equal to 2, and so on. Each time the loop is executed, the
algorithm executes the key operation of comparison one time. Hence, the algorithm makes
N - 1 comparisons each time the inner loop is executed. The outer loop is executed N - 1
times.
It is important to note that testing whether to end the loop may itself involve a key
operation. In this case (depending on the computer language and what looping command
is used), if the loop is executed N times, the test is usually performed N + 1 times, once