Computer Science Programming Basics in Ruby

7.5 Exercises

1. Radix sort, as presented, works for integers. Modify the algorithm in Example 7-4 to sort English names.

2. For each input sequence provided in the following list, state which presented comparison-based sort or sorts would require the fewest steps. Explain why.

   1. 5 2 4 3 1

   2. 1 2 3 4 5

   3. 5 4 3 2 1

3. You are provided a lengthy unsorted list and told to search it.

   1. Which search algorithm would you use?

   2. If you were told that you will need to search the list many times, would your search strategy change? If so, how?

   3. At which point would you change your approach if you were to change it?

4. The complexity of the comparison-based sorting algorithms presented, on the average case, is . Design a comparison-based sorting algorithm with a lower complexity. What is the underlying premise that lowers its complexity?

5. Generate a 100-element list containing integers in the range 0–10. Sort the list with selection sort and with radix sort.

   1. Which is faster? Why?

   2. Try this again, but with 10,000 elements. Note the relative difference. Why does it exist?