Page 217 - Discrete Mathematics and Its Applications

196 3 / Algorithms

Algorithm 3 proceeds by successively narrowing down the part of the sequence being
searched. At any given stage only the terms from a i to a j are under consideration. In other
words, i and j are the smallest and largest subscripts of the remaining terms, respectively.
Algorithm 3 continues narrowing the part of the sequence being searched until only one term
of the sequence remains. When this is done, a comparison is made to see whether this term
equals x.

Sorting

Ordering the elements of a list is a problem that occurs in many contexts. For example, to produce
a telephone directory it is necessary to alphabetize the names of subscribers. Similarly, producing
a directory of songs available for downloading requires that their titles be put in alphabetic order.
Putting addresses in order in an e-mail mailing list can determine whether there are duplicated
addresses. Creating a useful dictionary requires that words be put in alphabetical order. Similarly,
generating a parts list requires that we order them according to increasing part number.
Suppose that we have a list of elements of a set. Furthermore, suppose that we have a way to
order elements of the set. (The notion of ordering elements of sets will be discussed in detail in
Section 9.6.) Sorting is putting these elements into a list in which the elements are in increasing
order. For instance, sorting the list 7, 2, 1, 4, 5, 9 produces the list 1, 2, 4, 5, 7, 9. Sorting the
list d, h, c, a, f (using alphabetical order) produces the list a, c, d, f, h.
An amazingly large percentage of computing resources is devoted to sorting one thing
or another. Hence, much effort has been devoted to the development of sorting algorithms.
A surprisingly large number of sorting algorithms have been devised using distinct strate-
gies, with new ones introduced regularly. In his fundamental work, The Art of Computer
Programming, Donald Knuth devotes close to 400 pages to sorting, covering around 15
different sorting algorithms in depth! More than 100 sorting algorithms have been de-
vised, and it is surprising how often new sorting algorithms are developed. Among the
newest sorting algorithms that have caught on is the the library sort, also known as the
gapped insertion sort, invented as recently as 2006. There are many reasons why sort-
Sorting is thought to hold
ing algorithms interest computer scientists and mathematicians. Among these reasons are
the record as the problem
solved by the most that some algorithms are easier to implement, some algorithms are more efficient (either
fundamentally different in general, or when given input with certain characteristics, such as lists slightly out of
algorithms! order), some algorithms take advantage of particular computer architectures, and some al-
gorithms are particularly clever. In this section we will introduce two sorting algorithms,
the bubble sort and the insertion sort. Two other sorting algorithms, the selection sort
and the binary insertion sort, are introduced in the exercises, and the shaker sort is in-
troduced in the Supplementary Exercises. In Section 5.4 we will discuss the merge sort
and introduce the quick sort in the exercises in that section; the tournament sort is in-
troduced in the exercise set in Section 11.2. We cover sorting algorithms both because
sorting is an important problem and because these algorithms can serve as examples
for many important concepts.

THE BUBBLE SORT The bubble sort is one of the simplest sorting algorithms, but not one
of the most efficient. It puts a list into increasing order by successively comparing adjacent
elements, interchanging them if they are in the wrong order. To carry out the bubble sort, we
perform the basic operation, that is, interchanging a larger element with a smaller one following
it, starting at the beginning of the list, for a full pass. We iterate this procedure until the sort is
complete. Pseudocode for the bubble sort is given as Algorithm 4. We can imagine the elements
in the list placed in a column. In the bubble sort, the smaller elements “bubble” to the top as
they are interchanged with larger elements. The larger elements “sink” to the bottom. This is
illustrated in Example 4.

EXAMPLE 4 Use the bubble sort to put 3, 2, 4, 1, 5 into increasing order.