Assignment VI

Due date April 3 for paper assignment, April 8 for program

1. From text: exercises R-4.9, R-4.10.

2. From text: problem C-4.9

2.The purpose of this question is to examine some of the optimizations for quicksort that we mentioned in class.

a) As a baseline, implement in-place quicksort (full code given p.248, feel free to translate it into another language) and test it for a few arrays of size 100,000.

b) Remove the recursive calls, and use a linked structure to keep track of the array fragments that remain to be sorted. Compare the execution times of versions a) and b).

c) In class we indicated that quicksort is not very useful for small arrays, and that below a certain threshold (around 7 elements) it is preferable to use a "naive" algorithm such as selection or insertion sort. Make this modification to your algorithm, by calling naive_sort whenever the size of the array to be sorted is smaller than the treshold. Experiment with values of the threshold from 3 to 10 to find the best value.