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