In this C programming assignment is given the driver.h and another file cntSort.c , in cntSort we have to implement an algorithm, Let n be the number of elements to be sorted. Bubble sort and quicksort assume that we can compare any pair of elements and find out, in constant time, which one is larger and which one is smaller. They make no assumption on the values of the elements. Counting sort assumes the elements are integers between 0 and m, and m is much smaller than n. For example, let m be 3, and n be 10. Then the elements can be 0, 1, or 2, and we have ten of them. unsigned data[10] = {0, 2, 1, 1, 0, 2, 2, 0, 1, 1}; unsigned count[3]; Counting sort uses an array unsigned count[m] and initializes all elements in count to zero. Then we scan the array data. When we see a number data[i], this number is used as the index to the array count, and the corresponding count is incremented. After we finish scanning the array data, we have count[0] == 3, count[1] == 4, and count[2] == 3. How do we construct the sorted array from these counts? We write 0 for count[0] times, 1 for count[1] times, and 2 for count[2] times. Bubble sort takes O(n2) time in the worst case, and quicksort takes O(n lg n) time on average. Loosely speaking, quicksort is faster than bubble sort.

// Driver

#include #include #include #include #include #include

/* getopt.h */ extern char *optarg;

/* stdlib.h */ extern void srand48(long seed); extern double drand48(void);

/* this function is implemented in cntSort.c */ extern void cntSort(unsigned m, unsigned n, unsigned data[]);

/* comparison function for qsort() */ static int cmpUnsigned(const void *a, const void *b) { return *(unsigned *)a - *(unsigned *)b; }

int main(int argc, char* argv[]) { unsigned m, n, *data, *qsorted, i; struct timeval start, stop; float msec; long seed; int c;

/* command line options * ./cntSort -m mValue -n nValue -s seedValue * m default 64 * n default 2^20, 1M * seed default 2018 */ m = 64; n = 1 << 20; seed = 2018; /* process optional command line arguments */ while ((c = getopt(argc, argv, "m:n:s:")) != -1) { switch (c) { case 'm': sscanf(optarg, "%u", &m); break; case 'n': sscanf(optarg, "%u", &n); break; case 's': sscanf(optarg, "%ld", &seed); break; default: break; } } printf("m %u, n %u, seed %ld ", m, n, seed);

/* seeding the pseudorandom number generator */ srand48(seed);

/* allocate memory -- remember to free up them later */ data = (unsigned *)malloc(sizeof(unsigned) * n); qsorted = (unsigned *)malloc(sizeof(unsigned) * n);

/* initialize data */ for (i = 0; i < n; i++) qsorted[i] = data[i] = (unsigned) floor(drand48() * m);

/* time qsort */ gettimeofday(&start, NULL); qsort((void *)qsorted, n, sizeof(unsigned), cmpUnsigned); gettimeofday(&stop, NULL); msec = (stop.tv_sec - start.tv_sec) * 1000 + (stop.tv_usec - start.tv_usec) / 1000; printf("quicksort takes %.2f msec ", msec);

/* time cntSort */ gettimeofday(&start, NULL); cntSort(m, n, data); gettimeofday(&stop, NULL); msec = (stop.tv_sec - start.tv_sec) * 1000 + (stop.tv_usec - start.tv_usec) / 1000; printf("cntSort takes %.2f msec ", msec);

/* verify cntSort works correctly */ for (i = 0; i < n; i++) if (data[i] != qsorted[i]) { fprintf(stderr, "data differs from qsorted at the %u-th element ", i); exit(1); } /* free up memory */ free(qsorted); free(data);

return 0; }

// Main program to create the algorithm

#include

void cntSort(unsigned m, unsigned n, unsigned data[]) { unsigned *count;

/* allocate memory */ count = (unsigned *)malloc(sizeof(unsigned) * m);

/* free up memory */ free(count); }