1. Implement Selection Sort algorithm in a function with the function prototype void selectionSort (std::vector int> &v); and test it on a small vector of integers. 2. Implement the Quick Sort algorithm in a function with the function prototype void quickSort(std::vector &v); 3. Implement the Merge Sort algorithm in a function with the function prototype void merge Sort (std::vector Ev) 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 integers for nu 1000, 2000, 4000, 8000, 16000, 32000. Time how long selectionsort, quicksort and merge Sort 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 no1000, 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 m1000 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 Qin) be the time it takes for quicksort to sort n elements. Let Min) be the time it takes for merge Sort 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. S(n) smem Q(n) Q(n) (n log2n) mem M M(n) Mn) (n logan) Y 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,000. 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(n) whereas quicksort for the average case and merge Sort should be in logan). Try to graph: a. n vs. Sin) b. n vs. Qin) cnvs. Min). Does your data of the table support the theory that Selectionsort is O(n) that Quicksort is in logan) for the average case and that merge sort is Ofn logan)? 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. Submissions Make sure that your code is neat and is well commented Check that all of your programs work the way they are intended to work by running them with different A 4 ENG 2008-02-26 1G