CS 3343 Analysis of Algorithms, Fall 1996 Assignment 5

Due Tuesday, November 26 in class at 2 PM.

In each case assume that the values to be sorted are integers that are not necessarily unique and are stored in an array. The values should be sorted in ascending order. Your program should not assume that the values have a known maximum or minimum value. Instrument your code to separately count the number of comparisons made, the number of aritmetic operations performed, and the number of words of memory moved. Use global variables for the three counts but do not use any other global variables in your programs. Output the three counts and their sum.

You will make 12 runs for each sort, for a total of 36 runs and collect the data as described below. You will be handing in a number of tables which must be neatly produced and clearly labeled.

For each sort, test it on an array of 10 integers in the range 0 to 100,000 which are randomly generated with drand48(). Then test the program on 100 integers generated in the same range. For each test, print out the original list and then print out the sorted list. Each of these printouts should contain 10 numbers per line in right-justified columns of width 7. The output should be 70 columns wide.

Once you are sure that your sorts are working correctly, you can start collecting data. Each type of sort will be run 3 times on arrays of N integers for 4 different values of N. Do not print out the array for these runs.

For a given value of N, the first run will be on N integers in the range 0 to 100,000 which are randomly generated. Use drand48(). For the second run, used the sorted array generated by the first run. For the third run, reverse the order of the sorted integers before sorting. For each value of N you will make 3 runs, one on a general array, one on a sorted array, and one on an array sorted in reverse order.

Make runs for N=10, N=100, N=1000, and N=10,000.

Hand in the following:

• Your complete source code.
• Result of running lint on your source code. Make sure there are no lint warnings which are of concern.
• A printout of the results of your tests with arrays of size 10 and 100 on each program as described above which convinced you that your programs were running correctly.
• For each sort, three tables, one for each of the three types of input: random, sorted, and reverse sorted. Each table should have a column for each value of N and rows for counts of each of the types of operation counts including the total operation count. There should be nine tables, each with 16 numbers entered. For each table make your best guess at the order of the total number of operations performed.
• One summery table corresponding to your run with N=10,000 giving the total operation count. There should be a column for each type of input: random, sorted, and reverse sorted and a row for each type of sort.