Computer Science 269
Introduction to Data Structures
Fall 2000
Assignment 5 Due Tuesday, October 31, 2000

In this programming assignment, you will implement some sorting methods and measure their complexity, where complexity is defined to be the number of comparisions.
We proved in class that the comparison complexity of any comparison-sort algorithm is at least log2(n!). In practice, it's usually greater.
Write code to sort an array of integers. Your code should increment a counter each time two data values are compared, and not at any other time. Write code for selection sort (the very simple quadratic-time version), quicksort, heapsort, and one other comparison sorting method of your choice. Run each of these on each of the following data files: Write a table showing your results.
Submit to the Graduate Assistant by email.