Discrete Mathematics for Computer Science

304 CHAPTER 5 Analysis of Algorithms

concentrate on the selection at line 1. The condition at line^1 requires two comparisons.

The test in line 1 has two "selection blocks," lines^2 through^6 and lines^8 through 16, one

of which is then executed.

1. If the test in line 1 (C < A and C < B) returns the value true, one more comparison
   (line 2) is made.


2. Otherwise, the algorithm next tests (B < A and B < C) given in line 8, which requires
   two more comparisons. Then, whether this condition is true or false, the code makes
   exactly one more comparison (line 9 or line 15). This gives a total of three comparisons
   if the test of line 1 fails.
   Now, translate this information into the notation of complexity. The notation says that
   F 1 (B 1 ) is the number of comparisons needed to execute lines 2 through 6, the "true range"
   of the test in line 1. Let F 2 (B 2 ) be the number of comparisons needed to execute lines 8
   through 16, the "false range" of that test. G(I) is the number of comparisons needed to
   execute the test in line^1 itself, which is^2 for all I. As we noted above, FI(B 1 ) = 1, and
   F 2 (B 2 ) = 3. So,

G(I) + max{FI(B1), F 2 (B 2 )} = 2 + 3 = 5

The entire algorithm makes at most five comparisons on any input data. (This is the same

upper bound as the worst case for the Ordering Three Values II algorithm.) Again, this

algorithm is 0(l).

Suppose, however, the procedure Swap were chosen as the key operation instead of

the comparison operation. The third algorithm makes at worst two calls to Swap, whereas

the other two algorithms will actually make three calls to Swap if the list is exactly out of

order. This illustrates a potential pitfall of the method described here. If one chooses the

key operations badly, then the results can be misleading. The examples above illustrate a

potential trade-off. One sorting algorithm may require fewer comparisons but more calls to

Swap than another may require. Which algorithm is better may depend on the data being

sorted and the computers being used.

In the case of sorting algorithms, the key operations chosen are usually either the op-

eration of interchanging (swapping) two elements in memory or determining which of two

elements is larger (comparing), since those operations tend to determine the time consump-

tion of most sorting algorithms. If both comparisons and interchanges are chosen as key

operations, then the analysis is quite realistic for most sorting algorithms.

5.3.3 An Algorithm Illustrating Repetition

One would never expect to write an algorithm to sort a three-element list. If you want

to sort an n-element list where n is at least 5, it is impractical to write an algorithm like

the ones previously discussed, since the algorithm gets too long. Nevertheless, the second

algorithm we present is easily generalized into an algorithm called BubbleSort, probably

the easiest of all sorting algorithms. Ease of coding is its primary virtue. It is also one of

the slowest sorting algorithms, although if "optimized," it can run quickly on certain very

special data sets.

The command

for i =1 to N

S