Homework No. 3
[ Sorting,
Sets, and Selection ]
The number of your particular task is the value of the
expression
faculty_number%6.
Write a complete program with at least one example in main function.
(0) Design and implement a stable version of the bucket-sort
algorithm for sorting a sequence of n
elements with integer keys taken from the range [0,N-1], for N > 2. Perform a series of
benchmarking time trials to test whether this method does indeed run in
O(n +
N) time. [P-10.2]
(1) Implement merge-sort and deterministic version of the quick-sort
algorithms and perform a series of benchmarking tests to see which one
is faster. [P-10.3]
(2) Implement deterministic and randomized versions of the quick-sort
algorithms and perform a series of benchmarking tests to see which one
is faster. [P-10.4]
(3) Implement an in-place version of insertion-sort and in-place
version of quick-sort. Perform benchmarking tests to determine the
range of values of n where
quick-sort is on average better than insertion sort. [P-10.5]
(4) Implement an in-place version of bubble-sort and in-place
version of quick-sort. Perform benchmarking tests to determine the
range of values of n where
quick-sort is on average better than
insertion sort.
(5) Implement the randomized quick-sort and quick-selection algorithms.
Design a series of benchmarking tests to test the relative speed of
solving the selection problem either directly, by quick-select method,
or indirectly, by first sorting via quick-sort method and then
returning the element of requested rank. [P-10.7]