Chapter Review 155
(b) If Harry, Hermione, and Frodo are all experienced in potions and each of them
prefers potions to at least one other job, then hire them all for potions.
- Given an array Names with n elements,
Names[0], Names[l],.... Names[n - 1]
each containing a surname (family name), the following algorithm finds the largest
name (in alphabetical order). Write an invariant for the loop.
temp = Names[O]
fori=l,2,...,n-1
if Names[i] > temp
temp = Names[i]
Output temp
- Challenge: Look up Hoare's quicksort algorithm. Write loop invariant assertions that
make the logic of quicksort easy to understand. You may also want preconditions
and postconditions. A precondition is a formula that the programmer assumes will
be true when an algorithm is invoked (called); the programmer announces that if the
precondition is not true, then the algorithm probably will not do what it is supposed
to do. A postcondition is a formula expressing something that is supposed to be true
after the algorithm finishes-assuming the preconditions are satisfied, of course.
