CHAPTER 13

Questions

1. The more complex code written for a binary search results in searches that are much faster for large data sets.

2. In general, simple sorts have a performance proportional to the square of the number of items, whereas advanced sorts have a performance proportional to nlog2 (n).

3. The big - O notation signifies the proportionality mentioned above. Literally, it is "order of".

4. "In place" sorting refers to sorting back into the same data space as the unsorted items were presented to the sorter. Usually, this means that an array of unsorted items is presented, and the same array is returned, now sorted. This is in contrast to sorting, say, from one array to another.

5. None of the sorts other than Shell's are named after a person.

6. Left as an exercise for the student.

7. Answers may reference sorting railroad boxcars by load, date, number, origin, destination, or name of railroad. Similar considerations could be applied to airline passengers, taxpayers, customers, suppliers, students at a school, employees, etc.

8. Such conditions prevent an invalid array reference. Without it, the count would go outside the appropriate range of the array.

9. When answering this question, you should try to give a theoretical reason, then run the code and see what happens.

10. The issue here is the need to copy data. Any method that does so will suffer a performance hit as the size of the data item increases. If a value parameter is used for the array (because you're not sorting in place) data is copied when the procedure is entered.

11. Left as an exercise for the student.

12. Left as an exercise for the student.

Problems

Note: At this stage, students should not need any problem solutions.