Page 219 - Discrete Mathematics and Its Applications

198 3 / Algorithms

is not less than this element is found or until it has been compared with all j − 1 elements; the jth
element is inserted in the correct position so that the first j elements are sorted. The algorithm
continues until the last element is placed in the correct position relative to the already sorted list
of the first n − 1 elements. The insertion sort is described in pseudocode in Algorithm 5.

EXAMPLE 5 Use the insertion sort to put the elements of the list 3, 2, 4, 1, 5 in increasing order.

Solution: The insertion sort first compares 2 and 3. Because 3 > 2, it places 2 in the first position,
producing the list 2, 3, 4, 1, 5 (the sorted part of the list is shown in color). At this point, 2 and 3
are in the correct order. Next, it inserts the third element, 4, into the already sorted part of the list
by making the comparisons 4 > 2 and 4 > 3. Because 4 > 3, 4 remains in the third position.
At this point, the list is 2, 3, 4, 1, 5 and we know that the ordering of the first three elements
is correct. Next, we find the correct place for the fourth element, 1, among the already sorted
elements, 2, 3, 4. Because 1 < 2, we obtain the list 1, 2, 3, 4, 5. Finally, we insert 5 into the
correct position by successively comparing it to 1, 2, 3, and 4. Because 5 > 4, it stays at the end
of the list, producing the correct order for the entire list. ▲

ALGORITHM 5 The Insertion Sort.

procedure insertion sort(a 1 ,a 2 ,...,a n : real numbers with n ≥ 2)
for j := 2 to n
i := 1
while a j >a i
i := i + 1
m := a j
for k := 0 to j − i − 1
a j−k := a j−k−1
a i := m
{a 1 ,...,a n is in increasing order}

Greedy Algorithms

Many algorithms we will study in this book are designed to solve optimization problems.
The goal of such problems is to find a solution to the given problem that either minimizes or
“Greed is good ... Greed
maximizes the value of some parameter. Optimization problems studied later in this text include
is right, greed works.
Greed clarifies ...” – finding a route between two cities with smallest total mileage, determining a way to encode
spoken by the character messages using the fewest bits possible, and finding a set of fiber links between network nodes
Gordon Gecko in the film using the least amount of fiber.
Wall Street.
Surprisingly, one of the simplest approaches often leads to a solution of an optimization
problem. This approach selects the best choice at each step, instead of considering all sequences
of steps that may lead to an optimal solution. Algorithms that make what seems to be the “best”
choice at each step are called greedy algorithms. Once we know that a greedy algorithm finds a
feasible solution, we need to determine whether it has found an optimal solution. (Note that we
You have to prove that a
call the algoritm “greedy” whether or not it finds an optimal solution.) To do this, we either prove
greedy algorithm always
finds an optimal solution. that the solution is optimal or we show that there is a counterexample where the algorithm yields
a nonoptimal solution. To make these concepts more concrete, we will consider an algorithm
that makes change using coins.