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.
-
In the subject line of the message, write "CSC 269 HW 5"
-
Include your source code as well as input and output files.
-
The deadline is October 31 at 5:30 PM. No late homework will be accepted.
-
You will receive results by email.