Data Structures and Algorithms

Workshop 2 - 1998


The basic aims of this workshop are to You will need to write a simple program to generate lists of data to be sorted and then to time various sorting algorithms for a sufficient range of sizes of the data list to verify that the expected time complexity is observed.

You should augment your Collection class so that you can add two sorting methods:

So that you can verify that your sort algorithms are operating correctly, add another method: which verifies that the data is, in fact, sorted after the sort algorithm has been applied.

In order to make this code as general-purpose and useful as possible, you should ensure that the Collection constructor has an additional argument, the comparison function. This will be discussed in the lecture on Aug 10, so you can either defer worrying about it while you design the rest of the system (it involves a straightforward addition to the design) or test your tutor's memory of the definitely non-intuitive syntax required - alternatively read your C text or the lecture notes.

In order to understand the difference in the results that you obtain, you should instrument your algorithms to count the number of comparisons and the number of exchanges made. Note that although you can use the machine's library quicksort routine, qsort, initially, you will need to implement a version of your own by downloading the code from the notes in order to instrument the algorithm.

Think carefully about how you will add the instrumentation code and how you will obtain the statistics when the sort has completed. This should disturb the "normal" code as little as possible, so that the instrumented code runs in ordinary programs with no changes and still sorts correctly.

As a final part of this assignment, you should test the library quicksort algorithm to see if you can infer what type of pivot selection is used. (You can limit this to "naive" or otherwise - but anyone who can devise a technique which reliably detects what strategy is used under the "otherwise" heading is assured of 100% for this assignment (as long as no major design crimes are committed!).) Check the qsort library routine on another type of machine as a demonstration that your code is ANSI standard compliant and portable. If it is, then this shouldn't take more than 10 minutes: log into another machine (you can use any other one you like), recompile, re-run and you should have an answer! (Although using one of the fancy GUI compilers on a Windows machine will take more than 10 minutes to set the project up!)


Prepare a brief report which summarises your results. It should contain as a minimum, (The report should be plain ASCII text - not the native form of any word processor.)

This report should start by forming a hypothesis about your expected results. This should be followed by the actual results. The conclusion should provide a convincing argument as to why these results confirm your original hypotheses. It should also highlight and attempt to explain any discrepancies.

If you design your program efficiently, you will be able to get it to generate a table of data for you which you can paste directly into the report.

Submission Instructions will be available soon!