SEARCHING AND SORTING - Java Programming: From Problem Analysis to Program Design - page 935

3. a. Write a version of the sequential search algorithm that can be used to
search a sorted list.
b. Consider the following list:
5 12 17 35 46 65 78 85 93 110 115
Using the sequential search on ordered lists that you designed in (a), how many
comparisons are required to determine whether the following items are in the list
or not? (Recall that comparisons mean item comparisons, not index comparisons.)

35 60 78 120

i. ii. iii. iv.

4. Consider the following list:
2 10 17 45 49 55 68 85 92 98 110

Using the binary search (given in this chapter), how many comparisons are
required to determine whether the following items are in the list? Show the
values of first , last , and middle , and the number of comparisons after
each iteration of the loop.
a. 15 b. 49 c. 98 d. 99
5. Sort the following list using the selection sort algorithm as discussed in this
chapter. Show the list after each iteration of the outer for loop.
26, 45, 17, 65, 33, 55, 12, 18
6. Sort the following list using the selection sort algorithm as discussed in this
chapter. Show the list after each iteration of the outer for loop.
36, 55, 17, 35, 63, 85, 12, 48, 3, 66
7. Assume the following list: 5, 18, 21, 10, 55, 20
The first three keys are in order. To move 10 to its proper position, using
the insertion sort as described in this chapter, exactly how many key
comparisons are executed?
8. Assume the following list: 7, 28, 31, 40, 5, 20
The first four keys are in order. To move 5 to its proper position, using the
insertion sort as described in this chapter, exactly how many key compar-
isons are executed?
9. Assume the following list:
28, 18, 21, 10, 25, 30, 12, 71, 32, 58, 15
This list is to be sorted using the insertion sort algorithm as described in this
chapter. Show the resulting list after six passes of the sorting phase—that is,
after six iterations of the for loop.
10. Recall the insertion sort algorithm as discussed in this chapter. Assume the
following list of keys:
18, 8, 11, 9, 15, 20, 32, 61, 22, 48, 75, 83, 35, 3
Exactly how many key comparisons are executed to sort this list using the
insertion sort?

1
4