C++

1. Implement Selection Sort algorithm in a function with the function prototype

void selectionSort (int A[], int n);

2. Implement the Quick Sort algorithm in a function with the function prototype

void quickSort(int A[], int n);

3. Implement the Merge Sort algorithm in a function with the function prototype

void mergeSort(int A[], int W[], int n);

where W is an array of working storage (W has the same length as the array A).1 You may want to spend some time optimizing the base case of the recursion for quickSort and mergeSort because we want to make them as fast as we can.

When you are given a function prototype (as an interface for a function), you must use the function prototype given. However, you are free to overload the function to suit your algorithm.

4. Now, using the using the rand() function, generate arrays of random 15 bit or 30 bit random integers for n = 1000, 2000, 4000, 8000, 16000, 32000. Time how long selectionSort, quicksort and mergeSort take.

To get an accurate measure for the time for small values of n, you will need to repeat the experiment m times, that is, time how long it takes to sort an array of n values m times and then divide the total time T by m. For example, for n=1000, you may need to repeat the experiment m=100 times so that the total time is at least 1 time unit. For the fast algorithms, you may need to use m=1000 or more, to get an accurate time T.

5. Now let S(n) be the time it takes to sort n elements for selectionSort.

Let Q(n) be the time it takes for quickSort to sort n elements.

Let M(n) be the time it takes for mergeSort to sort n elements.

In a Word document, Excel document or in a text file, create a table of the following data which your program(s) will produce using the functions you developed in 1) 2) 3) and 4). Your program should generate all these values in a single execution of the program (Yes it all take a long time to run but is much easier than running it multiple times.

() () 2 () () ( log2 ) () () ( log2 )

1000

2000

4000

8000

16000

32000

So, for instance, the value y in the table above corresponds to the average time it takes to selection sort 2,000 integers divided by 2,0002 . In other words, y was computed by sorting with selection sort 2,000 integers, running the sorting m times and getting the average, and then dividing that average time by 4,000,000

6. Theoretically, selectionSort should be O(n2 ) whereas quickSort for the average case and mergeSort should be O(n log2n).

Try to graph: a. n vs. S(n) b. n vs. Q(n) c. n vs. M(n).

Does your data of the table support the theory that selectionSort is O(n2 ) that Quicksort is O(n log2n) for the average case and that merge sort is O(n log2n)? Justify your answer using your own data and discuss what you can infer from the table, particularly why the third, fifth, and seventh columns give such values. Note that we are doubling the n in the table above.