CS 1723 Section 1T, Summer 1998 Assignment 6

CS 1723 Section 1T, Summer 1998 Assignment 6: Sorting

For the following type of data:

#define KEY_SIZE	4
typedef char key[KEY_SIZE+1];

Write a function beginning with:

void sort (key v[], int n) {

that will sort the keys in ascending alphabetical order.

On runner in ~djimenez/cs1723/sorts there are some files:

Makefile mysort.c sorts.c sorts.h

Make a directory called sorts in your account and copy all of these files into that directory. Modify your copy of mysort.c to contain your sorting code (currently, it calls qsort; get rid of that part). When you type make, the Makefile provided will compile your code and link it with sorts.c to make a program called sorts that will test and grade your code.

Do not modify sorts.c, only mysort.c. The program sorts accepts a command line parameter that is either the word "-grade" or an integer less than or equal to 150,000.

If you give sorts an integer, it will tests your code for a randomly generated array of that size and compare the time it takes against the time qsort/strcmp takes. The -grade option tests your code against qsort for ten rounds of sorting different sized arrays and assigns a grade based on how well your sort did against qsort. You can examine the source code to see the details of the grading, but basically you get 5 points for doing as well as qsort, and anywhere up to 15 points for sorting up to 0.75 seconds faster than qsort.

Constraints and Hints

You are guaranteed that the strings in the array will all be of length exactly 4 (with a null terminator in the 5th position), and that all of the characters in the strings will be lowercase letters.
You may use any sorting algorithm you like, as long as you implement it in C yourself.
You may not use qsort. If you did, you would probably only get a 5 anyway.
You may use strcmp, but you might not want to since you would probably be using it a lot, and each function call incurs a small time penalty.
Your function must compile using the provided Makefile etc., and must correctly sort the data. sorts will exit if it detects that your function hasn't correctly sorted the data, and you will not have a grade.
The times reported by sorts are the amount of CPU time used by the program, not the amount of "wall clock" time. Since there are other users on the system, the actual running time of the program will be longer than the amount of CPU time used.
sorts will not process any arrays with more than 150,000 elements due to time and memory constraints on runner. This places on upper bound on the number of items your algorithm has to sort, and thus makes the asymptotic behavior of your sort somewhat less relevant. For example, radix sort may be asymptotically faster than heapsort, but it is not clear for any given implementations which one will be faster for an array of size 150,000.
Don't use something like bubble sort, selection sort, or insertion sort: these will be too slow and it will take forever to compute your bad grade.

How to turn it in (read this in advance)

You will be grading this program yourself. The Makefile provided has a line:

CFLAGS	=	-g

so that gcc will compile debugging information into your program. Change this to

CFLAGS	=	-O

to turn on compiler optimizations. Type make clean to get rid of old object files compiled with -g, then make again to compile with optimizations. Then type make turnin; this will run your function through 10 sets of data of increasing size, and use the times computed to assign a grade. Then your results and a copy of your mysort.c will be mailed to the instructor. Only do this once; to get an estimate of your grade before you are finished, just run sorts -grade.

If your program fails to compile or to sort properly, you will not be able to send the instructor a grade for this assignment, so make sure it works!

Note: compiling with optimizations can sometimes expose subtle bugs in your program that would not turn up with -g. You should try running your program with -O in the Makefile well before you intend to turn it in, in case one of these bugs manifests itself and you have to go fix it. You don't have to use -O, but optimization can only increase your grade.

It should go without saying that you shouldn't modify sorts.c or do anything else to artificially give yourself a better grade.

If you have any problems with this program, please contact the instructor. Don't wait until the last minute to begin this program.

This program is due by midnight, Tuesday July 28, 1998.