Sorting algorithms - Data Structures and Problem Solving Using Java - page 388

If you know more information about the items being sorted, you can
sort them in linear time. Show that a collection of N 16-bit integers
can be sorted in O ( N ) time. ( Hint: Maintain an array indexed from 0
to 65,535.)

8.17

The quicksort in the text uses two recursive calls. Remove one of the
calls as follows.
a.

8.18

Rewrite the code so that the second recursive call is uncondition-
ally the last line in quicksort. Do so by reversing the if / else , and
returning after the call to insertionSort .

b. Remove the tail recursion by writing a while loop and altering low .

Continuing from Exercise 8.18, after part (a),
a.

8.19

Perform a test so that the smaller subarray is processed by the
first recursive call and the larger subarray is processed by the sec-
ond recursive call.

b. Remove the tail recursion by writing a while loop and altering low

or high , as necessary.

c. Prove that the number of recursive calls is logarithmic in the

worst case.

Suppose that the recursive quicksort receives an int parameter, depth ,
from the driver that is initially approximately 2 log N .
a.

8.20

Modify the recursive quicksort to call mergeSort on its current
subarray if the level of recursion has reached depth . ( Hint: Decre-
ment depth as you make recursive calls; when it is 0, switch to
mergesort.)

b. Prove that the worst-case running time of this algorithm is

O ( N log N ).

c. Conduct experiments to determine how often mergeSort gets called.

d. Implement this technique in conjunction with tail recursion

removal in Exercise 8.18.

e. Explain why the technique in Exercise 8.19 would no longer be

needed.

An array contains N numbers, and you want to determine whether
two of the numbers sum to a given number K . For instance, if the
input is 8, 4, 1, 6 and K is 10, the answer is yes (4 and 6). A number
may be used twice. Do the following.
a.

8.21

Give an O ( N 2 ) algorithm to solve this problem.

b. Give an O ( N log N ) algorithm to solve this problem. ( Hint: Sort the

items first. After doing so, you can solve the problem in linear time.)

c. Code both solutions and compare the running times of your

algorithms.