# Data Structures and Algorithms

## Workshop 2 - 1998

### Sorting

The basic aims of this workshop are to
• compare various sorting routines.
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:

• HeapSort and
• QuickSort
So that you can verify that your sort algorithms are operating correctly, add another method:
• `int Sorted( Collection c );`
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!)

### Report

Prepare a brief report which summarises your results. It should contain as a minimum,