***USING C***

Compile and run the program with optimization, but with profiling for timing:

gcc -c -pg -O2 main.c gcc -c -pg -O2 bubbleSort.c gcc -c -pg -O2 quickSort.c gcc main.o bubbleSort.o quickSort.o -pg -O2 -o assign1-2

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?

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

Here I am attaching code for these files:

main.c

quickSort.c

insertionSort.c

header.h

Source code for main.c:

#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 char* temp = array[index0]; array[index0] = array[index1]; array[index1] = temp; }

// 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 do { printf("Please enter %s (%d-%d): ", descriptionCPtr, min, max); scanf("%d", &entry); } while(entry < min || entry > max);

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 insertion sort or 2 for quicksort",1,2); array = generateStringArray(arrayLen);

switch (choice) { case 1 : insertionSort(array,arrayLen); break;

case 2 : quickSort(array,arrayLen); break; }

print(array,arrayLen); releaseMem(array,arrayLen); return(EXIT_SUCCESS); }

Source code for quickSort.c:

#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); }

Source code for insertionSort.c:

#include "header.h"

// PURPOSE: To sort the 'arrayLen' strings in array 'array' with the // insertion-sort algorithm. No return value. void insertionSort (char** array, int arrayLen ) { int i; int j;

for (i = 0; i < arrayLen-1; i++) for (j = i+1; j < arrayLen; j++) if ( strncmp(array[i],array[j],strLen) > 0 ) swap(array,i,j); }

Source code for header.h:

#include #include #include

extern void swap();

extern int strLen;

extern void insertionSort(); extern void quickSort();

Thank you!