For the following algorithm foo, explain what it computes, state what the input size for analysis is, state what basic operations should be counted for analyzing it, state exactly how many operations are executed as a function of the input size, and state the efficiency class to which it belongs. Show your work and explain how you arrived at your answers.

void foo(vector& array) { size_t size = array.size(); for (size_t select_indx = 0; select_indx < size - 1; select_indx++) { int smallest_value = array.at(select_indx); size_t smallest_indx = select_indx; for (size_t compare_indx = select_indx + 1; compare_indx < size; compare_indx++) { if (array.at(compare_indx) < smallest_value) { smallest_value = array.at(compare_indx); smallest_indx = compare_indx; } } swap(array.at(smallest_indx), array.at(select_indx)); } } The built-in C++ swap function is extremely efficient, and you can count it as performing exactly two basic operations.

Write a C++ program that implements the algorithm above, counts the number of basic operations, and outputs the input size and the count of basic operations to the cerr stream. Your program must accept the size of the array as a single command line argument, it must produce exactly one line to cout that prints the contents of the array, space separated, after foo has been called, and it must produce exactly one line to cerr that prints the input size, a space, and a count of the basic operations. A run of your program must look exactly like this:

$ ./program 5 -145175 -9166 119534 350670 975235 5 12345 (except that you will have different values, and 12345 is not correct). For large input size, you will almost certainly want to redirect cout to /dev/null. For this program, you will probably use random numbers. To generate high-quality pseudorandom numbers, better than simple rand() can produce. Include the chrono and random system libraries, and use this code:

const int MAX_RANDOM_VALUE = 1000000; default_random_engine get_next_value (static_cast (chrono::system_clock::now().time_since_epoch().count())); uniform_int_distribution rng(-MAX_RANDOM_VALUE, MAX_RANDOM_VALUE); Then, when you need a random number, do a statement such as this: int random_value = rng(get_next_value); Run the program in such a way that the algorithm is exercised many times with many different inputs and input sizes, and capture the count data in a file. Show the command(s) you used to do this.

Use a plot of input size vs. basic operations, along with one or more standard functions properly scaled, to illustrate the analysis you did.