The goal of this problem is to compare the experimental running times of the two sorting algorithms. (?Insertion Sort and Merge Sort programs listed below)

a) Now that you have proven that your code runs correctly using the data.txt input file, you can modify the code to collect running time data. Instead of reading arrays from a file to sort, you will now generate arrays of size n containing random integer values from 0 to 10,000 and then time how long it takes to sort the arrays. We will not be executing the code that generates the running time data so it does not have to be submitted to TEACH or even execute on flip. Include a text copy of the modified code in the written HW submitted in Canvas.

b) Use the system clock to record the running times of each algorithm for n = 1000, 2000, 5000, 10,000, . You may need to modify the values of n if an algorithm runs too fast or too slow to collect the running time data. If you program in C your algorithm will run faster than if you use python. You will need at least seven values of t (time) greater than 0. If there is variability in the times between runs of the same algorithm you may want to take the average time of several runs for each value of n.

?Probably just need to change the main function to do this.

?Insertion Sort

//Description: Take an input file and use insertion sort to sort // and place in an output file

#include #include #include

using namespace std;

void insertion_sort(int arr[], int x) //function that uses insertion sort { int key; int i; int j;

for(i = 1; i < x; i++){ key = arr[i]; j = i - 1;

/*Elements moved into the array that are *greater than key to a position one position ahead *of current position*/

while(j >= 0 && arr[j] > key){ arr[j+1] = arr[j]; j = j - 1; }

arr[j + 1] = key; } }

int main() { ifstream in("data.txt"); if(in.fail()){ cout << "Error: File did not open" << endl; return 0; }

ofstream out("insert.out");

int x;

//read in size of the array while(in >> x){ int *arr = new int[x]; int j = 0; while(j < x){ in >> arr[j]; j++; } //call insert sort function insertion_sort(arr, x);

//write to the ouput file for(int i; i < x; i++){ out<

in.close(); out.close(); cout<<"Data has been sorted and place in file insert.out" << endl;

return 0; }

Merge Sort

//Description: This program is to use merge sort to sort an undetermined amount of // numbers from a file, sort them and output in new file

#include #include #include

using namespace std;

/*Function splits the merge sort in to half*/ void merge(int *a, int bottom, int top, int middle){ int i = bottom; int j = middle + 1; int k = 0; int temp[top - bottom + 1];

//Merges parts into temp[] while(i <= middle && j <= top){ if(a[i] , a[j]){ temp[k] = a[i]; k++; i++; } else{ temp[k] = a[j]; k++; j++; } } //place ramining values from bottom to middle in sorted array while(i <= middle){ temp[k] = a[i]; k++; i++; }

//place ramaining values from middle+1 to top in sorted array while(j <= top){ temp[k] = a[j]; k++; j++; }

//move sorted array from temp to official array for(i = bottom; i <= top; i++){ a[i] = temp[i - bottom]; } }

/*splits array recursively down to signle units*/ void merge_sort(int *a, int bottom, int top){ int middle;

if(bottom < top){ middle = (bottom + top)/2;

//split in half merge_sort(a, bottom, middle); merge_sort(a, middle + 1, top);

//merges everything back together merge(a, bottom, top, middle); } }

int main() { ifstream in("data.txt"); if(in.fail()){ cout << "Error: File did not open" << endl; return 0; }

ofstream out("merge.out");

int x;

//read in size of the array while(in >> x){ int *arr = new int[x]; int j = 0; while(j < x){ in >> arr[j]; j++; } //call insert sort function merge_sort(arr, 0, x - 1); //write to the ouput file for(int i; i < x; i++){ out<