Analysis of Algorithms: Sorting Competition

Deadline: April 26

The purpose of the project is to implement a fast algorithm for sorting large arrays, using the C language with gcc compiler, under Unix. You may work alone or in groups of unlimited size; a group should submit one program, and all members of the group will get the same grade.

Task

You need to code a procedure for sorting an array a[0..n-1] of integer numbers, according to the following specification:

        void sort (int* a, int n);

This procedure and its subroutines should reside in a file sort.c, which should not contain a main function. Your procedure will be evaluated on 1,000,000-element arrays, with values between -5,000,000 and 5,000,000.

You may download an example sort.c file with insertion sort; note that this example sorting is too slow for 1,000,000-element arrays, and you should implement a faster algorithm. You may use the tester.c file for testing your code; it includes procedures for generating random arrays and checking the correctness of sorting. After you implement a sorting procedure, put tester.c and sort.c in the same directory and compile them:

        gcc -O -funroll-loops -o tester tester.c

If you then run tester, it will apply your procedure to ten arrays, and output the number of correctly sorted arrays and the average sorting time. When debugging, you may control the array size, range of values, and number of tests, by re-defining the following constants in tester.c:
 
SIZE size of the array a
MIN lower bound for the range of values
MAX upper bound for the range of values
TESTS number of arrays to be sorted

Bug reports

If you find bugs in tester.c or in the example sort.c file, please send e-mail to the instructor at eugene@csee.usf.edu; the bugs will be fixed within 24 hours.

Submission

E-mail your source file sort.c to the teaching assistant, at xcheng@csee.usf.edu, by 9:30am on April 26. All submitted code should be in sort.c; you should not send tester.c or any other files. The subject line should say "Sorting Competition" and include the last names of the group members, in the alphabetical order:

        Sorting Competition: Cheng, Fink

You do not need to submit a print-out of your code or a written report. Note that the code is due by 9:30am even if your machine or network is down. Try to e-mail it in advance, to ensure that computer "emergencies" do not affect your submission. If you e-mail your code within 48 hours after the deadline, then you may earn up to five points for correct sorting, but you will not enter the speed competition.

Grading

Your grade will depend on correctness and efficiency of sorting. First, your procedure will be tested on ten arrays and graded for correctness, out of five points. This grade will be proportional to the number of correctly sorted arrays. For example, if your procedure correctly sorts seven arrays, then you will get 7/10 = 3.5 points. It must sort all ten arrays in sixty minutes, using at most 64 Mbytes memory; if sorting takes more time or memory, it will earn no points. If your procedure correctly sorts all ten arrays, within sixty minutes, then it will enter the speed competition and may earn additional points. The bonus for the first, second, or third place is in reverse proportion to the group size. If your group includes n students, you will get the following reward:
 
First place 30/n points
Second place 20/n points
Third place 10/n points

If the speed of your program is within the factor of five from the first place, you will get additional five points. For example, suppose that your group consists of two members, your program has correctly sorted all ten arrays, it has earned the third place in the competition, and its speed is within the factor of five from the first place; then, your total grade is 5 + 10/2 + 5 = 15.

Back to the Algorithms home page