Department of Mathematics and Computer Science

Machine Problem 8

Math 61 D. C. Smolarski, S.J. Winter, 2000

Data Structure Concepts: ADVANCED SORTING ALGORITHMS

40 points
DUE: Noon, ***TUESDAY***, March 7, 2000

PLEASE WORK ALONE ON THIS FINAL PROGRAM, SINCE IT IS MERELY A PROGRAM TO COPY CODE FROM THE BOOK AND GET IT RUNNING WITH ONLY SLIGHT MODIFICATIONS.

You are to implement HEAPSORT (as given in Ford and Topp [pp 690-703], or elsewhere), and use as your input file, mp8in.inp in my ma61 subdirectory on "math" (see MP2 for instructions on how to copy such a file) or at this link. There are 999 records in the file to be sorted, two numbers per record (line). You should sort according to the first number, but carry the second number along as being associated with the first number. When printing out the sorted list, you should put more than one record on a line (perhaps 5-8), in order not to have 11 pages of output.

PLEASE!!!!! DO NOT PRINT OUT THE INPUT FILE!!! YOU WOULD MERELY BE WASTING 11 PAGES!!!!!

Please note that Ford and Topp spread the code over several pages, defining the class "heap" earlier with its functions, and only toward the end giving the code for heapsort. Once again, if this code is confusion, it might be better to modify it rather than attempt to use it in its entirety in the book.

ALSO NOTE that you need to modify the data structure slightly since you are actually sorting a structure with two components according to the value of the first component.

This page is maintained by Dennis C. Smolarski, S.J., dsmolarski@math.scu.edu. Last changed: 12 January 2000.