#include  #include  #include  #include  const char DATA_FILE_NAME[] = "TestData.txt"; typedef struct functionRuntimes { char *szName; /ame of the function being tested double **arrRuntimes; //run times double *arrAvg; //average runtime int iNumRepeats; /umber of times to repeat each test size int iNumTestCaseSizes; /umber of test case sizes int *arrTestSizes; //array containing the test case sizes } functionRuntimes; //Functions used to test the runtimes functionRuntimes timeAlgorithm( char*, int, int, int[], void (*f)(FILE *) ); FILE *generateTestInput( int, int, int ); void computeAvg( functionRuntimes fRT ); void printRuntimeTable( functionRuntimes fRT ); void freeFunctionRuntimes( functionRuntimes fRT ); //Functions whose runtime will be tested (and helper functions) void insertionSortInitial( FILE* input ); void insertionSort( int* points, int low, int high ); void quickSortOptInitial( FILE* input ); void quickSortOpt( int* points, int low, int high ); int partition( int* points, int low, int high ); void mysteryRuntime1( FILE* input ); void mysteryRuntime2( FILE* input ); void mysteryRuntime3( FILE* input ); /* * Provided code - DO NOT CHANGE THIS METHOD * (if you make alterations plan to revert them before submission) */ int main( int argc, char *argv[] ) { functionRuntimes fRT; int sizes1[] = { 2000, 4000, 8000, 16000, 32000, 64000, 128000}; srand(time(0)); fRT = timeAlgorithm("Insertion Sort", 10, 3, sizes1, insertionSortInitial ); printRuntimeTable(fRT); freeFunctionRuntimes(fRT); fRT = timeAlgorithm("quicksort (uses insertion sort when sorting 1 ) { size = size/2; array[size/2] = array[size]; } free(array); } /* provided code - DO NOT CHANGE */ void mysteryRuntime2( FILE* input ) { int temp; int size; int n; int i=0; int *array; if( fscanf( input, "%d", &size ) != 1 ) { exit(-1); } array = (int *) malloc( size*sizeof(int) ); if( array == NULL ) { exit(-1); } while( fscanf( input, "%d", &temp ) == 1 && i1; n/=1.01 ) { array[n-1] = array[n]; } } free(array); } /* provided code - DO NOT CHANGE */ void mysteryRuntime3( FILE* input ) { int temp; int size; int i=0, j=0; int *array; if( fscanf( input, "%d", &size ) != 1 ) { exit(-1); } array = (int *) malloc( size*sizeof(int) ); if( array == NULL ) { exit(-1); } while( fscanf( input, "%d", &temp ) == 1 && i=size ) { j++; i=0; } } free(array); } /* * Provided code - DO NOT CHANGE THIS METHOD */ void insertionSortInitial( FILE* input ) { int i; int size; int *array; fscanf( input, "%d", &size ); array = (int *) malloc( size*sizeof(int) ); for( i=0; iarray[i]) { printf("Not sorted!"); exit(-1); } }*/ free(array); } /* * Provided code - DO NOT CHANGE THIS METHOD */ void insertionSort( int* points, int low, int high ) { int i, j; double temp; for( i = low+1; i  low && points[j]array[i]){ printf("Not sorted!"); exit(-1); } }*/ free(array); } /* * Provided code - DO NOT CHANGE THIS METHOD */ void quickSortOpt( int* points, int low, int high ) { if( high =low && points[j] > pivotValue ) { j--; } if(i  This program prints a table of runtimes (these are displayed in seconds) for given functions on arrays. The program tests different array sizes to establish a relationship between input size and runtime. It tests each array size multiple times and then takes an average of the times. Here are example calls to the timing functions: int sizes[] = { 1000, 2500, 5000, 7500, 10000); char stri = "Insertion Sort": char str2 = "quicksort (uses insertion sort when sorting