***UTILIZING C***

Compile and run the program without any extra optimizations, but with profiling for timing:

gcc -c -pg -O0 main.c gcc -c -pg -O0 bubbleSort.c gcc -c -pg -O0 quickSort.c gcc main.o bubbleSort.o quickSort.o -pg -O0 -o assign1-0

Run the program twice timing it both times, and answer the following:

How for 65536 strings of length 8 how many self seconds did bubbleSort() take?

How for 65536 strings of length 8 how many self seconds did quickSort_() take?

Code:

These two files need a main() to run their functions bubbleSort() and quickSort(). Then all three C files need a header file to inform them of what the others have that they need. Please finish both the main() and header.h.

Please note! Not everything needs to be shared.

main() needs bubbleSort() and quickSort()

Both bubbleSort() and quickSort() need swap() and strLen.

Code for header.h:

#include  #include  #include  // YOUR CODE HERE 

Code for main.c:

//This file defines the variable strLen and function swap() needed for the program

#include "header.h" #define TEXT_LEN 256 // PURPOSE: To tell the length of the strings to sort. int strLen; // PURPOSE: To swap the strings in 'array[]' at indices 'index0' and 'index1'. // No return value. void swap (char** array, int index0, int index1 ) {  // YOUR CODE HERE } // PURPOSE: To repeatedly ask the user the text "Please enter ", followed // by the text in 'descriptionCPtr', followed by the numbers 'min' and // 'max', and to get an entered integer from the user. If this entered // integer is either less than 'min', or is greater than 'max', then // the user is asked for another number. After the user finally enters // a legal number, this function returns that number. int obtainIntInRange(const char* descriptionCPtr, int min, int max ) { int entry; char text[TEXT_LEN];  // YOUR CODE HERE return(entry); } // PURPOSE: To generate the array of strings. char** generateStringArray (int numStrings ) { char** array = (char**)calloc(numStrings,sizeof(char*)); int i; int j; for (i = 0; i < numStrings; i++) { array[i] = (char*)malloc(strLen); for (j = 0; j < strLen; j++) { array[i][j] = (rand() % 16) + 'A'; } } return(array); } void print (char** array, int arrayLen ) { int i; int j; for (i = 0; i < arrayLen; i++) { for (j = 0; j < strLen; j++) { putchar(array[i][j]); } putchar(' '); } } void releaseMem (char** array, int arrayLen ) { int i; for (i = 0; i < arrayLen; i++) { free(array[i]); } free(array); } int main () { int arrayLen; char** array; int choice; arrayLen = obtainIntInRange("number of strings",1,65536*16); strLen = obtainIntInRange("length of each string",1,16); choice = obtainIntInRange("1 for bubble sort or 2 for quicksort",1,2); array = generateStringArray(arrayLen); switch (choice) { case 1 : bubbleSort(array,arrayLen); break; case 2 : quickSort(array,arrayLen); break; } print(array,arrayLen); releaseMem(array,arrayLen); return(EXIT_SUCCESS); }

Source code for bubbleSort.c

#include "header.h" // PURPOSE: To sort the 'arrayLen' strings in array 'array' with the // bubble-sort algorithm. No return value. void bubbleSort (char** array, int arrayLen ) { int i; int haveExchanged; do { haveExchanged = 0; for (i = 0; i < arrayLen-1; i++) if ( strncmp(array[i],array[i+1],strLen) > 0 ) { swap(array,i,i+1); haveExchanged = 1; } } while (haveExchanged); }

Source code for quickSort:

#include "header.h" int partition (char** array, char* pivot, int lo, int hi ) { lo--; hi++; while (1) { do { lo++; } while (strncmp(array[lo],pivot,strLen) < 0); do { hi--; } while (strncmp(array[hi],pivot,strLen) > 0); if (lo >= hi) break; swap(array,lo,hi); } return(hi); } int pivot (char** array, int lo, int hi ) { char* atLo = array[lo]; char* atMid = array[(lo+hi)/2]; char* atHi = array[hi]; if ( ((strncmp(atLo,atMid,strLen)<=0) && (strncmp(atMid,atHi,strLen)<=0)) || ((strncmp(atLo,atMid,strLen)>=0) && (strncmp(atMid,atHi,strLen)>=0)) ) return((lo+hi)/2); if ( ((strncmp(atMid,atLo,strLen)<=0) && (strncmp(atLo,atHi,strLen)<=0)) || ((strncmp(atMid,atLo,strLen)>=0) && (strncmp(atLo,atHi,strLen)>=0)) ) return(lo); return(hi); } void quickSort_ (char** array, int lo, int hi ) { if (lo < hi) { int left; int right; int p = pivot(array,lo,hi); p = partition(array,array[p],lo,hi); quickSort_(array,lo,p); quickSort_(array,p+1,hi); } } // PURPOSE: To sort the 'arrayLen' strings in array 'array' with the // quick-sort algorithm. No return value. void quickSort (char** array, int arrayLen ) { quickSort_(array,0,arrayLen-1); }

Please show screenshots of output!

Thank you!