Problem $2-1.$

HEAPSORT$($A$)$

BUILD$-$MAX$-$HEAP$($A$)$

for i$=$A$.$length downto $2$

exchange A$[1]$ with A$[$i$]$

A$.$heapsize $=$ A$.$heapsize $-1$

MAX$-$HEAPIFY$($A$,1)$

$(10$ points$)$ Argue the correctness of HEAPSORT using the following loop invariant:

At the start of each iteration of the for loop of lines $2-5,$ the subarray $A[1$dotsi$]$ is a

max$-$heap containing the i smallest elements of $A[1$dotsn$],$ and the subarray $A[i+1$dotsn$]$

contains the $n-$i largest elements of $A[1$dotsn$],$ sorted.

Make sure that your loop invariant fulfills the three necessary properties.

Problem $2-2.(10$ points$)$ What is the running time of HEAPSORT on an array $A$ of length $n$ that

is already sorted in increasing order? What about decreasing order?

Problem $2-3.(5$ points$)$ Show that the worst$-$case running time of HEAPSORT is $(nlgn).$

Problem $2-4.(5$ points$)$ Show that the running time of QuICKSORT is $(n^2)$ when the array $A$

contains distinct elements and is sorted in decreasing order.