Just number 2.

2. (20 pts) Collect worst-, average-, and best-case run time data associated with each algorithm. (a) Pick at least five vector lengths ranging from small to large. These sizes should cover a range that begins to show asymptotic growth of the run time of these sorting algorithms. The lengths 10, 100, 1000, 5000, and 10000 are probably a good place to start though this will depend somewhat on your machine. (b) For each length and each type of vector (worst-, average-, and best-case), generate 50 vectors. (c) Sort these vectors using each algorithm and collect the run times. You may want to save these values in a separate output file. (d) In the end, you should have 12 (3 4) sets of times, one for each case/algorithm pair. Each set should include a total of 250 (5 50) run times, 50 times for each vector size. (e) To use plotData (described in the next section) this data should be stored in three CSV files, one for worst-, average-, and best-case times. Each line in these files should be in the form algorithm, size, time where algorithm is one of bubble, insertion, selection, or quick. For example, several lines of a best_case_times.csv file might look something like this:

bubble,10,7e-07

insertion,10,6e-07

selection,100,2.67e-05

quick,10000,0.0143179

Below is the reference for the above part.

For the following questions, make sure to follow the pseudocode discussed in class. 1. (10 pts) Implement a function that checks whether or not a vector is sorted. 2. (20 pts) Implement bubble sort. 3. (22 pts) Implement insertion sort. 4. (22 pts) Implement selection sort. 5. (26 pts) Implement quicksort. 1 2 Testing and Experiments 1. (20 pts) Write a function that runs each of the sorting algorithms on ten random vectors of length 100, collects the run times, verifies that the sorting was successful, and prints out the minimum, mean, standard deviation, and maximum of the run times. Example output for a single sort might look something like this: ************************ Bubble sort on 10 vectors of length 100 Sorting successful Minimum: 1 sec; Mean: 1 sec; Standard deviation: 1 sec; Maximum: 1 sec ************************ This should be what is run by default after making your programming and running ./a.out in the terminal.