Consider the following code, where $A$ is an array of integers of size $\text{size(A)}$ with values $A[0] \;to\;A[\text{size(A)-1}]$, and $\text{reverse(A,i,j)}$ reverses the segment $\text{A[i]}$ to $\text{A[j]}$ if $\text{i<=j}$ and has no effect otherwise. For instance, if $A=[0,1,2,3,4,5]$, then $\text{reverse(A,2,4)}$ would modify $A$ to $[0,1,4,3,2,5].$
def mystery(A)
{
for j in [0,1,...,size(A)-1]
{
p=j;
for i in [j,j+1,...,size(A)-1]
{
if A[i]>A[p]
{
p=i;
}
reverse(A,j,p);
}
}
}
- What is the effect of this code on an input array $A$?
- Suppose $\text{size(A)}$ is $1000$. How many times is the test $\text{A[i]>A[p]}$ executed?
