Assignment 6

Due date:

Late assignments will be penalized 10% per day, and will not be accepted after .

1. Hand In

Each student is required to do this assignment individually and to hand in the following:

A disk containing only two files: the source listing and executable for the program in the assignment.
Printouts of the program and the output it produces in test data of your own choice.

Place these items in a 9"x11" envelope, with the following information clearly marked on the outside of the envelope:

Name, Student Number, Assignment Number, Course Number (T26)

Assignments which are not in an envelope will not be marked

Deposit your envelope in .

Marking Scheme

Programming standards: 10pt, Question 1a: 18pt, Questions 1b, 1c and 1d: 8pt, Question 2: 18pt, Total: 70pt.

Your program must conform to the programming standards. These are described in a separate sheet.

2. Program Handout

In this assignment, you are given a complete implementation of the abstract type `list'. You must use the implementation to write sorting functions. These functions must be at the `application' level: that is, they must be written completely independently of the exact manner in which lists are implemented: they must do all their list manipulations using the abstract list operations defined in the list specification.

Note that the main program writes out information about how much memory has been allocated by your procedures but not returned to the global pool. These numbers should always be 0: if they are not, you have bugs to fix.

The program handout consists of 2 files: Partial6.c and Partial6.h. The only file you should modify is Partial6.c. Partial6.h is automatically included and supplies an appropriate testing procedure for questions 1a, 1c, 1d and 2 - there is no testing procedure for question 1b. In order to get appropriate testing procedure for the question you are working on, you must modify accordingly the 2nd macro definition at the top of file Partial6.c. For example, to get the testing procedure for question 1a, it should be:

        #define QUESTION1a

whereas, for question 2 it should be:

        #define QUESTION2

3. Question 1a

Write a procedure merge meeting this specification:

Inputs: two lists, L1 and L2.
Outputs: L1', L2' (i.e. L1 and L2 are changed), and two integers: Nc, Njs
Preconditions: L1 and L2 are sorted (in increasing order)
Postconditions: L1' is the result of merging L1 and L2. L2' is undefined. Nc is the total number of times two list elements were compared during the merging process. Njs is the total number of join and split operations that were performed during the merging process.
Your procedure should do as few splits and joins as possible, and it should not use the insert operation.
Hint: it is probably simplest to write merge recursively.

The specification given above is slightly inconvenient to work with. Instead, we change the postconditions to be:

Either L1' is the result of merging L1 and L2, and L2' is undefined.
Or (the other way around) L2' is the result of merging L1 and L2, and L1' is undefined.

Since we need to know which one is the result, we further require merge to be a function that returns this result as its value. Thus, after executing l1 = merge(l1,l2,Nc,Njs), l1 contains the result of the merge and the `other' list has been destroyed. In other words, at this point, (1) either l2 has been destroyed, or (2) the old l1 has been destroyed and now l1==l2.

4. Question 1b

Write a procedure general_sort that meets this specification:

Inputs: a list, L, and a procedure cut_in_two that meets the specification below
Outputs: L' (i.e. L is changed), and two integers: Nc, Njs
Preconditions: L is defined
Postconditions: L' is sorted in increasing order. Nc is the total number of times two list elements were compared during the sorting process, including the comparisons made by the merge and cut_in_two procedures. Njs is the total number of join and split operations that were performed during the sorting process, including the joins and splits done by the merge and cut_in_two procedures.
The procedure must use the general sorting strategy (described in detail in class):
1. use the procedure cut_in_two to divide L into two pieces
2. recursively sort the two pieces
3. merge the results (use the procedure written in Question 1a).

The procedure cut_in_two meets this specification:

Input: a list, L1
Outputs: L1' (i.e. L1 is changed), L2 (a list), and two integers, Nc and Njs
Preconditions: L1 has 2 or more elements
Postconditions: neither L1' nor L2 is empty, and collectively they contain all the elements of L1 (and nothing else). Nc is the number of times two list elements were compared during the cut_in_two process. Njs is the total number of join and split operations that were performed during the cut_in_two process.

5. Question 1c

Write a procedure merge_sort that implements the mergesort algorithm simply by calling general_sort with an appropriate cut_in_two procedure (which you must also write). merge_sort should return the sorted list L' and the integers Nc and Njs returned by general_sort.

6. Question 1d

Write a procedure insertion_sort that implements the insertion sort algorithm simply by calling general_sort with an appropriate cut_in_two procedure (which you must also write). insertion_sort should return the sorted list L' and the integers Nc and Njs returned by general_sort.

7. Question 2

Choose five different lengths of lists ranging from small (e.g. 10) to large (as large as you can and still finish executing in a few minutes), with reasonably-spaced intermediate values.

For each of these list lengths, run the program written for question 1 five times using a different random number seed each time. Average the results.

Plot the average number of comparisons and the average number of splits/joins for the two sorting algorithms (merge sort and insertion sort) as a function of the length of the list.

Which algorithm is better for sorting short lists?
Which will be better for sorting extremely long lists?

Justify your answers.