Quick Sort is a popular sorting algorithm because it usually achieves op- timal O(nlogn) running time in practice. However, in the worst case, the running time can be quadratic. The method to choose the pivot is crucial to avoid the worst cases. The purpose of this homework is to evaluate exper- imentally the performance of Quick Sort for different methods of choosing the pivot, and compare with Insertion Sort, which is simpler but quadratic in the worst case.

1. Write a method that implements Insertion Sort (pseu- docode attached, do not use other versions).

2. Write methods for two versions of Quick Sort, depending on how the pivot is chosen from each subarray to be sorted, as follows.

(a) Choose the pivot from the last position of the subarray being sorted (pseudocode attached).

(b) Choose the pivot at random. That is, choose a position of the subarray being sorted at random, and take its content as the pivot.

The pseudocode for Quick Sort is also attached, do not use other ver- sions. You have to modify the way that the pivot is chosen for part 2b.

3. Write a test program that measures the running time of the above three methods while sorting n numbers. Use n as big as your system tolerates (start trying with n = 1000000 and increase it until you run out of space or memory for any of the 3 algorithms). Use three types of inputs: already sorted in increasing order, already sorted in decreasing order, and an input with the numbers generated at random. Fill in the following chart with the running times observed.

4. (20 points) Draw conclusions from the values observed. Are the mea- surements significantly different for some