# Introduction to Algorithms and Data Structures, Episode 3

## Lecture, February 18

Subject : Comparison sorting vs non-comparison sorting algorithms

Text : CLRS chap. 7.1-3; chap. 8.1-2; Read also chapters 8.3-8.4 on radix sort and bucket sort. This material is fairly accessible and it will help you to follow the next lecture. Adventurous students are welcome to study the careful average-case performance analysis of Quicksort in Section 7.4.

Prerequisites : Understanding of O-notation and log n

Comments : This week we shall study Quicksort—the most popular in-place sorting algorithm ever. Then we shall occupy ourselves with establishing a general lower bound for the time usage of sorting algorithms. Finally we will look at non-comparison sorting techniques.

Time : Friday, 18 February, 9:00–12:00, Room 2A12

Tutorial : 13:00–16:00, Room 3A14

## Assignments

• CLRS exercises 7.1-1 (H), 7.1-2 (H), 7.1-3 (H), 7.1-4 (H), pp. 148-149.
• CLRS exercises 7.2-2 (H), 7.2-3 (H), 7.2-4(H) p. 153.
• CLRS Problem 7-1 (M) p. 159 (omit the e part)
• CLRS exercise 8.1-1, p. 167.
• CLRS exercises 8.2-1, 8.2-3(M), 8.2-4 (E), p. 170.
• CLRS exercise 8-1 (D), p. 178.

The mandatory assignments should be handed in no later than March 2, at 13.00.

## 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.