Java Software Structures, 4th Edition Exercise Solutions, Ch. 9
Chapter 9 Exercise Solutions
EX 9.1. Compare and contrast the linear search and binary search algorithms by searching
for the numbers 45 and 54 in the following list:
3 8 12 34 54 84 91 110
Searching for 45, which isn’t in the list, requires eight comparisons in a linear search to
EX 9.2. Using the list from Exercise 9.1, construct a table showing the number of
comparisons required to sort that list for each of the sort algoirthms (selection
sort, insertion sort, bubble sort, quick sort, and merge sort).
Sort Algorithm
Number of Comparisons
Selection sort
7 + 6 + 5 + 4 + 3 + 2 + 1 = 28
Insertion sort
7
Bubble sort
7 + 6 + 5 + 4 + 3 + 2 + 1 = 28
Quick sort
(2+7) + (2+6) + (2+5) + (2+4) + (2+3) + (2+2) = 39
Merge sort
1 + 1 + 2 + 1 + 1 + 2 + 4 = 12
EX 9.3. Consider the same list from Exercise 9.1. What happens to the number of
comparisons for each of the sort algorithms if the list is already sorted.
The processing of selection and bubble sort, as written, is independent of the original
configuration of the items in the list, and therefore remain O(n2). But given that the data
is originally sorted, the inner loop of the insertion sort will only make one comparison
EX 9.4. Given the following list:
trace the execution for:
a. selection sort
Min 1, swap with 90: 1 8 7 56 123 235 9 90 653
Min 7, swap with 8: 1 7 8 56 123 235 9 90 653
Min 8, swap with 8: unchanged
Min 9, swap with 56: 1 7 8 9 123 235 56 90 653
Java Software Structures, 4th Edition Exercise Solutions, Ch. 9
b. insertion sort
Insert 1: 1 90 8 7 56 123 235 9 653
Insert 9: 1 7 8 9 90 56 123 235 653
Insert 56: 1 7 8 9 56 90 123 235 653
c. bubble sort
After first iteration: 8 7 56 90 123 9 1 235 653
After fifth iteration: 7 8 1 9 56 90 123 235 653
d. quick sort
e. merge sort
EX 9.5. Given the resulting sorted list from exercise 9.4, trace the execution for a binary
search, searching for the number 235.
Given the sorted list:
1 7 8 9 56 90 123 235 653
A binary search for the number 235 would proceed as follows:
EX 9.6. Draw a UML class diagram for the SortPhoneList program.
EX 9.7. Hand trace a radix sort for the following list of five-digit student ID numbers,
assuming that each digit must be between 1 and 5.
Digit
1s Position
1
22331 32131
2
54312 21212
4
5
Digit
10s Position
1
54312 21212
2
13224 12123
4
5
Digit
100s Position
Java Software Structures, 4th Edition Exercise Solutions, Ch. 9
1
32131 12123
2
13224 21212
4
5
Digit
1,000s Position
1
21212
2
22331 32131 12123
4
54355 54312
5
Digit
10,000s Position
1
13224 12123
2
22331 21212
4
5
54355 54312
EX 9.8. What is the time complexity of a radix sort?
The time complexity of a radix sort is c * n, or O(n), but only works for specifically