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?
***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('\n');
}
}
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
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 <stdlib.h>
#include <stdio.h>
#include <string.h>
extern void swap();
extern int strLen;
extern void insertionSort();
extern void quickSort();
Thank you!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
