Introduction to Algorithms and Data Structures, Episode 3

Programming Assignments

This week's programming assignments will improve your understanding of recursion and Quicksort, it is divided in several simple steps.

Assignment 3.1

Begin with implementation of Quicksort in Java (or any other programming language of choice). You should provide a function qsort which accepts an array of integer numbers and sorts the array in place in increasing order. Use a simple pivot selection scheme as in CLRS (for example the rightmost element in the sorted part of the array).

Test the implementation on various data inputs, in particular: on single element input, on sorted input, reversed sorted input, random input. Try random inputs of 2-3 sizes and measure running times.

Now try another pivot selection mechanism, for example a median-of-three (choose three elements of the sorted array and reject the lowest and largest of these three) or random pivot selection as in Randomized-Quicksort (chap. 7.3). Does this change influence the speed of your implementation on random permutation of input? You should remember to run comparisons on the very same random inputs as before (it may be convenient to store them in a file, or easier run the two tests in a single program run)

Assignment 3.2

You should now have a good implementation of Quicksort. In this exercise we ponder the space complexity of your implementation. In recursive algorithms the stack depth incurres an implicit space cost. Efficient algorithms cannot allow inefficient stack usage. Read and understand CLRS Problem 7-4 Stack depth for Quicksort p.162. Omit question a, give answer to question b.

Modify your qsort function, (i) creating a tail-recursive version of Quicksort, as shown in the pseudo code on p.162. Then reply to question c and (ii) implement an improved tail recursive version, which only uses n log n stack space in the worst case. Hint: the depth of recursion can be controlled by controlling the size of recursive subproblem (size of input to the recursive call). Also you should use the same Partition function in both cases.

Note, that you can test the improvement introduced by version (ii), by sorting the input, which causes variant (i) to use linear amount of space on the stack. You can measure the improvement either introducing an explicit counter for depth of recursion, or producing a large input and measuring the total use of memory for both implementations (this can get distorted in Java, because of automatic memory management). It is by far the easiest to carry on the experiments with the simplest pivot selection scheme, as originally defined in chapter 7.1 in CLRS.

Observe that a clever compiler would perform step (i) automatically. Nevertheless elimination of tail recursion is an important programming practice (especially if your compiler does not provide it, like most Java compilers). In general step (ii) cannot be performed automatically.