COMP 3270
Homework 3 Solutions
1. (7 points) Heapsort
Show the array A after the algorithm Min-Heap-Insert(A, 6) is operates on the Min Heap implemented in array A=[6, 8, 9, 10, 12, 16, 15, 13, 14, 19, 18, 17]. In order to solve this problem you have to do some of the thinking assignment on the Ch.6 lecture slides. But you do not have to submit your solutions to those thinking assignments. Use your solutions to determine the answer to this question and provide the array A below.
A=[6, 8, 6, 10, 12, 9, 15, 13, 14, 19, 18, 17, 16].
2. (22 points) Quicksort
(a) (6 points)
Quicksort can be modified to obtain an elegant and efficient linear (O(n)) algorithm QuickSelect for the selection problem.
Quickselect(A, p, r, k)
{p & r – starting and ending indexes; to find k-th smallest number in non-empty array A; 1≤k≤(r-p+1)}
1 if p=r then return A[p]
else
2 q=Partition(A,p,r) {Partition is the algorithm discussed in class}
3 pivotDistance=q-p+1
4 if k=pivotDistance then
5 return A[q]
6 else if k