Random Permutations

Please see exercise 2.8 on page 72 of the textbook. The problem presents three different algorithms for pupulating an array of size N with a random permutation of the values from 1 through N.

Implement each of these three algorithms as its own function in source file permutations.cpp (the book says to write three different programs, but for this assignment implement each as a function, not its own program). Three empty functions are provided for your code. Implement algorithms 1, 2, and 3 in functions permutations1, permutations2, and permutations3 respectively. You may also include any support functions you feel you need within the same source file (note that any support functions should be declared as static functions).

A main function is provided in main.cpp which includes code to select which algorithm to use, create an array of the some desired size, call the appropriate function (your implementation) with timing, then reports the timing and determines if the implementation was successful. Do not modify the main function or any source files other than permutations.cpp.

File permutations.cpp includes a search function for your convenience. (A search is necessary for algorithm 1.) Also included, in another source file, are three convenience functions for generating random integers. The functions are:

unsigned int randint() Returns a random integer in the range of 0 to 2 billion +.

unsigned int randint(unsigned int max) Returns a random integer in the range of 0 through max-1.

unsigned int randint(unsigned int min, unsigned int max) Returns a random number in the range of min through max inclusive.

In addition to the implementation of these three algorithms:

Give a Big-Oh analysis of each of these algorithms. State the Big-Oh nature of the algorithm and describe how you arrived at your conclusion.

Run the program for each algorithm and for each of the following array sizes and report the run-times:

For algorithm 1: 5000, 10000, 20000, 40000

For algorithm 2: 100000, 200000, 400000, 800000, 1600000, 3200000, 6400000

For algorithm 3: 500000, 1000000, 2000000, 4000000, 8000000, 16000000, 32000000

Compare your analysis with the actual run-times. Do the actual run-times match up with your Big-Oh analysis?

Prepare your answers to the items above in Markdown form in file README.md.

#include "permutations.h" #include "timer.h" #include #include #include #include using namespace std;

int main() { // Initialize the RNG. srand(time(0));

// Set precision for timer output. cout << fixed << setprecision(2);

// Prompt for and input algorithm. int algo = 0; cout << "Enter algorithm (1, 2, or 3): "; cin >> algo; if (algo < 1 || algo > 3) exit(1);

// Prompt for and input array size. int size = 0; cout << "Enter array size: "; cin >> size; if (size < 1) exit(1); cout << " ";

// Create the array and initialize with zeros. int *array = new int[size]; for (int i = 0; i < size; i++) array[i] = 0;

// Call the selected algorithm to fill array with values. Timer timer; switch (algo) { case 1: permutations1(array, size); break; case 2: permutations2(array, size); break; case 3: permutations3(array, size); break; }