Heap Sort Assignment

1 Programming Assignment
The assignment is to implement the heap sort algorithm with the following inout and output
specifications:
Input: An array A of n integers.
Output: The elements of A will be written back to A in sorted order.
Pseudocode for heap sort is given below:
Algorithm 1 HeapSort(A,n)
H Empty Heap
for i = 0; 1; : : : ; n − 1 do
H:insert(A[i])
end for
for i = 0; 1; : : : ; n − 1 do
A[i] H:removeMin()
end for
A Java template has been provided containing an empty function HeapSort, which takes an
integer array A as its only argument. Your task is to write the body of the HeapSort function. You
must use the provided Java template as the basis of your submission, and put your implementation
inside the HeapSort function in the template. You may not change the name, return type or
parameters of the HeapSort function. The main function in the template contains code to help you
test your implementation by entering test data or reading it from a file. You may modify the main
function, but only the contents of the HeapSort function will be marked, since the main function
will be deleted before marking begins. Please read through the comments in the template file before
starting.
12 Test Datasets
A set of input files containing test data are available under the ’Data’ tab on conneX. You should
ensure that your implementation gives the correct answer on these test files before submitting. It
may also be helpful to test your implementation on a variety of other inputs, since the posted data
may not cover all possible cases.
3 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated
testing (using large test arrays similar to the ones posted on conneX) and human inspection.
Score Description
0 - 3 Submission does not compile or does not conform to the provided
template.
3 - 15 The implemented algorithm is not heap sort or is substantially
inaccurate on the tested inputs.
16 - 20 The implemented algorithm is heap sort but does not have a
Θ(n log n) running time or is inaccurate on some inputs.
21 - 25 The implemented algorithm is correct and has a Θ(n log n) running time.
To be properly tested, every submission must compile correctly as submitted, and must be based
on the provided template. If your submission does not compile for any reason (even trivial
mistakes like typos), or was not based on the template, it will receive at most 3 out
of 25.