Answers to Selected Exercises Chapter 1

Chapter 10

(a) BubbleSort

4	5	7	10	43	14	18	23	19	66
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

4	5	7	10	18	43	19	23	66	14
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

7	10	23	43	18	4	19	5	66	14
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

4. (a) bubble sort

(b) selection sort

(c) insertion sort

7. The correct answer is (c).

10. (a) Bubble sort is O(N) if the values are already sorted, and if the algorithm stop processing when the sorting is complete (like ShortBubble).

(b) None.

(c) QuickSort is O(N ²) if the values are already sorted and the split algorithm causes the array to be split into one element and the rest of the array.

13. (a) True

(b) False. HeapSort is better for nearly sorted data than QuickSort.

(c) True

16. The correct answer is (b).

19. The code is identical to the one in the book with the relational operator in the comparison changed.

22. Declare an array indexed from 0 through 99. Use the slots in the array as counters for that percentile score; that is, the slot indexed by 0 is the counter for percentile scores of 0; the slot indexed by 2 is the counter for percintile scores of 2; and so on. To produce the required output, go through the array from 99 down to 0, printing the loop counter as many times as there are values in that slot.

25. (a) for the best case. O(1)

(b) for the worst case. O(N²)

28.

dataValues

14	27	95	12	26	5	33	15	9	99
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

sortedValues

5	9	12	14	15	26	27	33	95	99
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

Values	Search dataValues sequentially	Search sortedValues sequentially	Binary- Search sortedValues	Search tree
15	8	5	1	4
17	10	6	3	4
14	1	4	4	1
5	6	1	3	3
99	10	10	4	4
100	10	10	4	4
0010	1	3	3

31.

[0]	90	140	620
[1]
[2]
[3]	153	393
[4]
[5]	145	285	395
[6]	66	126	566
[7]	47	87	177
[8]	467	735

34. The correct answer is (a)

37. (a) 50

(b) 50

40. The correct answer is (c).