Page 218 - Discrete Mathematics and Its Applications

3.1 Algorithms 197

First pass 3 2 2 2 Second pass 2 2 2
2 3 3 3 3 3 1
4 4 4 1 1 1 3
1 1 1 4 4 4 4
5 5 5 5 5 5 5

Third pass 2 1 Fourth pass 1
: an interchange
1 2 2
3 3 3
4 4 4 : pair in correct order
5 5 5 numbers in color
guaranteed to be in correct order

FIGURE 1 The Steps of a Bubble Sort.

Solution: The steps of this algorithm are illustrated in Figure 1. Begin by comparing the first two
elements, 3 and 2. Because 3 > 2, interchange 3 and 2, producing the list 2, 3, 4, 1, 5. Because
3 < 4, continue by comparing 4 and 1. Because 4 > 1, interchange 1 and 4, producing the list
2, 3, 1, 4, 5. Because 4 < 5, the first pass is complete. The first pass guarantees that the largest
element, 5, is in the correct position.
The second pass begins by comparing 2 and 3. Because these are in the correct order, 3 and 1
are compared. Because 3 > 1, these numbers are interchanged, producing 2, 1, 3, 4, 5. Because
3 < 4, these numbers are in the correct order. It is not necessary to do any more comparisons
for this pass because 5 is already in the correct position. The second pass guarantees that the
two largest elements, 4 and 5, are in their correct positions.
The third pass begins by comparing 2 and 1. These are interchanged because 2 > 1, produc-
ing 1, 2, 3, 4, 5. Because 2 < 3, these two elements are in the correct order. It is not necessary to
do any more comparisons for this pass because 4 and 5 are already in the correct positions. The
third pass guarantees that the three largest elements, 3, 4, and 5, are in their correct positions.
The fourth pass consists of one comparison, namely, the comparison of 1 and 2. Because
1 < 2, these elements are in the correct order. This completes the bubble sort. ▲

ALGORITHM 4 The Bubble Sort.
procedure bubblesort(a 1 ,...,a n : real numbers with n ≥ 2)
for i := 1 to n − 1
for j := 1 to n − i
if a j >a j+1 then interchange a j and a j+1
{a 1 ,...,a n is in increasing order}

THE INSERTION SORT The insertion sort is a simple sorting algorithm, but it is usually
not the most efficient. To sort a list with n elements, the insertion sort begins with the second
element. The insertion sort compares this second element with the first element and inserts it
before the first element if it does not exceed the first element and after the first element if it
exceeds the first element. At this point, the first two elements are in the correct order. The third
element is then compared with the first element, and if it is larger than the first element, it is
compared with the second element; it is inserted into the correct position among the first three
elements.
In general, in the jth step of the insertion sort, the jth element of the list is inserted into
the correct position in the list of the previously sorted j − 1 elements. To insert the jth element
in the list, a linear search technique is used (see Exercise 43); the jth element is successively
compared with the already sorted j − 1 elements at the start of the list until the first element that